Approximation algorithms for minimum norm and ordered optimization problems

DOI10.1145/3313276.3316322MaRDI QIDQ5212754zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, Chaitanya Swamy

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.05022

zbMATH Keywords

approximation algorithmclusteringload balancingminimum norm optimizationordered optimization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Abstract: ${\displaystyle }$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 $ell$ loads, for any $ell$. We give a $(2+varepsilon)$-approximation for the so-called ordered load-balancing problem. $$ 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). $$ 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.

Recommendations

• Stochastic load balancing on unrelated machines
• Online load balancing on related machines
• Stochastic load balancing on unrelated machines
• Constant-factor approximation for ordered k-median
• Algorithm Theory - SWAT 2004

Cited in

(28)

• Constant-time RMESH algorithms for the range minima and co-minima problems
• Approximation algorithms for clustering with dynamic points
• Reverse greedy is bad for \(k\)-center
• Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
• Ordered optimal solutions and parametric minimum cut problems
• On clustering with discounts
• scientific article; zbMATH DE number 5871159 (Why is no real title available?)
• All-norms and all-L_p-norms approximation algorithms
• Approximating Minimum Linear Ordering Problems
• HYPER-MINIMIZATION IN O(n²)
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• All-norm approximation algorithms
• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• Approximating Minimization Diagrams and Generalized Proximity Search
• Approximation algorithms for clustering with dynamic points
• Approximate multi-matroid intersection via iterative refinement
• Universal Algorithms for Clustering Problems
• Tight approximation algorithms for ordered covering
• Improved bounds for distributed load balancing
• Budget-feasible mechanism design: simpler, better mechanisms and general payment constraints
• Computing job-tailored degree plans towards the acquisition of professional skills
• Robust min-max (regret) optimization using ordered weighted averaging
• Universal algorithms for clustering problems
• Minimum-norm load balancing Is (almost) as easy as minimizing makespan
• Dimension-free parameterized approximation schemes for hybrid clustering
• A parameterized approximation algorithm for the diversity-aware l-centrum problem
• Simultaneously approximating all norms for massively parallel correlation clustering
• New results on a general class of minimum norm optimization problems

This page was built for publication: Approximation algorithms for minimum norm and ordered optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212754)