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

clusteringapproximation algorithmload balancingminimum norm optimizationordered optimization

Mathematics Subject Classification ID

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

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

(19)

• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• Constant-time RMESH algorithms for the range minima and co-minima problems
• Approximate multi-matroid intersection via iterative refinement
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• Improved bounds for distributed load balancing
• Approximation algorithms for clustering with dynamic points
• Approximation algorithms for clustering with dynamic points
• Tight approximation algorithms for ordered covering
• Universal Algorithms for Clustering Problems
• Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
• scientific article; zbMATH DE number 5871159 (Why is no real title available?)
• On clustering with discounts
• All-norms and all-\(L_p\)-norms approximation algorithms
• Approximating Minimization Diagrams and Generalized Proximity Search
• Ordered optimal solutions and parametric minimum cut problems
• Approximating Minimum Linear Ordering Problems
• HYPER-MINIMIZATION IN O(n²)
• Reverse greedy is bad for \(k\)-center
• All-norm approximation algorithms

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)