Approximation Algorithms for Minimum Norm and Ordered Optimization Problems

In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k-clustering, opening k facilities induces an assignment cost vector across the clients. In this paper we consider the following minimum norm optimization problem : Given an arbitrary monotone, symmetric norm, find a solution which minimizes the norm of the induced cost-vector. This generalizes many fundamental NP-hard problems. We give a general framework to tackle the minimum norm problem, and illustrate its efficacy in the unrelated machine load balancing and k-clustering setting. Our concrete results are the following. bullet We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm k-clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. bullet In load balancing with unrelated machines, we give a 2-approximation for the problem of finding an assignment minimizing the sum of the largest ℓ loads, for any ℓ. We give a (2+varepsilon)-approximation for the so-called ordered load-balancing problem. bullet For k-clustering, we give a (5+varepsilon)-approximation for the ordered k-median problem significantly improving the constant factor approximations from Byrka, Sornat, and Spoerhase (STOC 2018) and Chakrabarty and Swamy (ICALP 2018). bullet Our techniques also imply O(1) approximations to the best simultaneous optimization factor for any instance of the unrelated machine load-balancing and the k-clustering setting. To our knowledge, these are the first positive simultaneous optimization results in these settings.