Universal Algorithms for Clustering Problems

DOI10.1145/3572840MaRDI QIDQ6075750zbMATH OpenOpenAlexFDO

Authors Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

clusteringuniversal algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: This paper presents universal algorithms for clustering problems, including the widely studied $k$-median, $k$-means, and $k$-center objectives. The input is a metric space containing all potential client locations. The algorithm must select $k$ cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm's solution and that of an optimal solution. A universal algorithm's solution $SOL$ for a clustering problem is said to be an $$-approximation if for all subsets of clients $C^{\prime }$, it satisfies $$, where $OPT(C^{\prime })$ is the cost of the optimal solution for clients $C^{\prime }$ and $MR$ is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of $k$-median, $k$-means, and $k$-center that achieve $(O(1),O(1))$-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other $el{l}_p$-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that $$-approximation is NP-hard if $alpha$ or $$ is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, $(O(1),O(1))$-approximation is the strongest type of guarantee obtainable for universal clustering.

Cites work

• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 2119701 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A local search approximation algorithm for \(k\)-means clustering
• A plant location guide for the unsure: approximation algorithms for min-Max location problems
• Algorithms for the universal and a priori TSP
• All-norms and all-L_p-norms approximation algorithms
• An analysis of approximations for maximizing submodular set functions—I
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Approximating k-median via pseudo-approximation
• Approximation Algorithms for 2-Stage Stochastic Optimization Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for minimum norm and ordered optimization problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Boosted sampling
• Clustering to minimize the maximum intercluster distance
• Improved lower and upper bounds for universal TSP in planar metrics
• Improved lower bounds for the universal and a priori TSP
• Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
• Least squares quantization in PCM
• Linear-time approximation schemes for clustering problems in any dimensions
• Local search heuristic for k-median and facility location problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Minimax regret p-center location on a network with demand uncertainty
• Minmax Regret Median Location on a Network Under Uncertainty
• Oblivious network design
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• Robust Combinatorial Optimization with Exponential Scenarios
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Sampling-based approximation algorithms for multistage stochastic optimization
• Set covering with our eyes closed
• Spacefilling curves and the planar travelling salesman problem
• Steiner tree approximation via iterative randomized rounding
• The Capacitated K-Center Problem
• The Euclidean \(k\)-supplier problem
• The ellipsoid method and its consequences in combinatorial optimization
• Thresholded covering algorithms for robust and max-min optimization
• Two-stage robust network design with exponential scenarios
• Universal approximations for TSP, Steiner tree, and set cover
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem

Cited in

(1)

• Simultaneously approximating all _p-norms in correlation clustering

This page was built for publication: Universal Algorithms for Clustering Problems

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