A technique for obtaining true approximations for \(k\)-center with covering constraints
From MaRDI portal
Publication:2118113
DOI10.1007/s10107-021-01645-yzbMath1489.90146OpenAlexW3017065416WikidataQ114228498 ScholiaQ114228498MaRDI QIDQ2118113
Rico Zenklusen, Adam Kurpisz, Haris Angelidakis, Georg Anegg
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01645-y
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)
Related Items (2)
Approximation algorithms for clustering with dynamic points ⋮ An approximation algorithm for diversity-aware fair \(k\)-supplier problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matroid and knapsack center problems
- Clustering to minimize the maximum intercluster distance
- Easy and hard bottleneck location problems
- Geometric algorithms and combinatorial optimization.
- On the existence of subexponential parameterized algorithms
- 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
- Fair Colorful k-Center Clustering
- On Partial Covering For Geometric Set Systems
- Improved approximation for tree augmentation: saving by rewiring
- Analytical approach to parallel repetition
- On the cost of essentially fair clusterings
This page was built for publication: A technique for obtaining true approximations for \(k\)-center with covering constraints
