A Technique for Obtaining True Approximations for k-Center with Covering Constraints
From MaRDI portal
Publication:5041734
DOI10.1007/978-3-030-45771-6_5zbMath1503.90103arXiv2007.03946OpenAlexW3160856740MaRDI QIDQ5041734
Georg Anegg, Adam Kurpisz, Rico Zenklusen, Haris Angelidakis
Publication date: 14 October 2022
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.03946
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (8)
On fair covering and hitting problems ⋮ Efficient algorithms for fair clustering with a new notion of fairness ⋮ On colorful vertex and edge cover problems ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Robust \(k\)-center with two types of radii ⋮ Robust \(k\)-center with two types of radii ⋮ Fair colorful \(k\)-center clustering
Cites Work
- Matroid and knapsack center problems
- Clustering to minimize the maximum intercluster distance
- Easy and hard bottleneck location problems
- Geometric algorithms and combinatorial optimization.
- LP-Based Algorithms for Capacitated Facility Location
- Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities
- A Best Possible Heuristic for the k-Center Problem
- Approximating capacitated k-median with (1 + ∊)k open facilities
- On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
- A Lottery Model for Center-Type Problems With Outliers
- Generalized Center Problems with Outliers
- Improved approximation for tree augmentation: saving by rewiring
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A Technique for Obtaining True Approximations for k-Center with Covering Constraints
