A Lottery Model for Center-Type Problems With Outliers

DOI10.1145/3311953zbMath1454.68182OpenAlexW2951891729MaRDI QIDQ4972682

David G. Harris, Khoa Trinh, Aravind Srinivasan, Thomas W. Pensyl

Publication date: 25 November 2019

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

Full work available at URL: https://doi.org/10.1145/3311953

zbMATH Keywords

approximation algorithmsrandomized rounding

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (13)

A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Fair Colorful k-Center Clustering ⋮ Unnamed Item ⋮ Approximation algorithms for clustering with dynamic points ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Efficient algorithms for fair clustering with a new notion of fairness ⋮ Fully dynamic \(k\)-center clustering with outliers ⋮ How to find a good explanation for clustering? ⋮ Fully dynamic clustering and diversity maximization in doubling metrics ⋮ Fully dynamic \(k\)-center clustering with outliers ⋮ Unnamed Item ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints ⋮ Fair colorful \(k\)-center clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid and knapsack center problems
• A local search approximation algorithm for \(k\)-means clustering
• Easy and hard bottleneck location problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• The Design of Approximation Algorithms
• Iterative Methods in Combinatorial Optimization
• Combinatorial geometries and torus strata on homogeneous compact manifolds
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation

This page was built for publication: A Lottery Model for Center-Type Problems With Outliers