Tutte Colloquium Seminar - Chaitanya Swamy

Title: Approximation Algorithms for Minimum-Norm Optimization Problems

Abstract:

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 that 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 for these problems. 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, and utilize this to obtain constant-factor approximation algorithms for  minimum-norm k-clustering and minimum-norm load balancing. These constitute the first constant-factor approximations for such a general suite of objectives. 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. 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.