Universal algorithms for clustering problems

DOI10.4230/LIPICS.ICALP.2021.70MaRDI QIDQ7241168zbMATH OpenFDO

Authors Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.70

zbMATH Keywords

\(k\)-center\(k\)-means\(k\)-medianclusteringuniversal algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A local search approximation algorithm for \(k\)-means clustering
• Algorithms for the universal and a priori TSP
• An analysis of approximations for maximizing submodular set functions—I
• Approximating k-median via pseudo-approximation
• 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
• Better guarantees for k-means and euclidean k-median by primal-dual algorithms
• Clustering to minimize the maximum intercluster distance
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• 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
• 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 discrete optimization and its applications
• Spacefilling curves and the planar travelling salesman problem
• Split and join: strong partitions and universal Steiner trees for graphs
• Steiner tree approximation via iterative randomized rounding
• The Capacitated K-Center Problem
• The ellipsoid method and its consequences in combinatorial optimization
• The Euclidean \(k\)-supplier problem
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem

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 Q7241168)