Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
share
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. ∙ 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. ∙ 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+ε)-approximation for the so-called ordered load-balancing problem. ∙ For k-clustering, we give a (5+ε)-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). ∙ 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.
READ FULL TEXT