In many optimization problems, a feasible solution induces a multidimensional cost vector. For example, in k-clustering, opening k facilities induces an assignment-cost vector indexed by the clients; in load-balancing, a schedule induces a load vector across the machines. Typically, one seeks a solution which either minimizes the sum of all entries, or the maximum entry of this vector, and the resulting problems (k-median, k-center, and makespan minimization) are classical NP-hard problems that have been extensively studied; given their NP-hardness, one seeks to design approximation algorithms, which are efficient algorithms that return provably near-optimal solutions. We consider a general optimization problem that we call minimum-norm optimization, where we are given an arbitrary monotone, symmetric norm, and we seek a solution that minimizes the norm of the induced cost vector. Monotone, symmetric norms are versatile and include L_p norms, Top-l norms (sum of the l largest coordinates in absolute value), and ordered norms (nonnegative linear combination of Top-l norms), and consequently, minimum-norm optimization models a wide variety of problems under one umbrella.
We give a general framework for tackling minimum-norm optimization, which leads to constant-factor approximation algorithms for minimum-norm k-clustering and minimum-norm load balancing on unrelated machines. To our knowledge, these constitute the first constant-factor approximations for such a general suite of objectives. Our techniques also yield improved guarantees for top-l and ordered norms, which have been studied for the k-clustering problem.
At a technical level, one of our chief insights is that minimum-norm optimization can be reduced to a special case that we call min-max ordered optimization, which highlights the fundamental role played by top-l norms. Both the reduction, and the task of devising algorithms for the latter problem, require a sparsification idea that we develop, which is of interest for ordered optimization problems. The main ingredient in solving min-max ordered optimization is a deterministic, oblivious rounding procedure for suitable LP relaxations of the load-balancing and k-clustering problems.
This is joint work with Deeparnab Chakrabarty. The talk will be self-contained.
