Universal Algorithms for Clustering Problems

DOI10.1145/3572840arXiv2105.02363OpenAlexW3178347017MaRDI QIDQ6075750

Debmalya Panigrahi, Arun Ganesh, Bruce M. Maggs

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Thresholded covering algorithms for robust and max-min optimization
• Algorithms for the universal and a priori TSP
• Clustering to minimize the maximum intercluster distance
• The ellipsoid method and its consequences in combinatorial optimization
• Two-stage robust network design with exponential scenarios
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• Set Covering with Our Eyes Closed
• Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
• Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
• All-Norms and All-L_p-Norms Approximation Algorithms
• A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Spacefilling curves and the planar travelling salesman problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Linear-time approximation schemes for clustering problems in any dimensions
• Boosted sampling
• Universal approximations for TSP, Steiner tree, and set cover
• Improved lower and upper bounds for universal TSP in planar metrics
• Oblivious network design
• Improved Lower Bounds for the Universal and a priori TSP
• A Best Possible Heuristic for the k-Center Problem
• An analysis of approximations for maximizing submodular set functions—I
• Minimax regret p-center location on a network with demand uncertainty
• Minmax Regret Median Location on a Network Under Uncertainty
• The Capacitated K-Center Problem
• A local search approximation algorithm for k-means clustering
• Least squares quantization in PCM
• The Euclidean k-Supplier Problem
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Local search heuristic for k-median and facility location problems
• Approximation algorithms for minimum norm and ordered optimization problems
• Approximation Algorithms for 2-Stage Stochastic Optimization Problems
• Steiner Tree Approximation via Iterative Randomized Rounding
• Robust Combinatorial Optimization with Exponential Scenarios
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating k-median via pseudo-approximation
• Algorithms - ESA 2003

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