A technique for obtaining true approximations for k-center with covering constraints

DOI10.1007/S10107-021-01645-YMaRDI QIDQ2118113zbMATH OpenOpenAlexWikidataFDO

Authors Georg Anegg, Haris Angelidakis, Adam Kurpisz, Rico Zenklusen

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-021-01645-y

zbMATH Keywords

\(k\)-centerapproximation algorithmsclusteringpolyhedral techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• A technique for obtaining true approximations for k-center with covering constraints
• An approximation algorithm for k-center problem on a convex polygon
• \(k\)-center problems with minimum coverage
• Computing and Combinatorics
• Approximation algorithms for the k-center problem: an experimental evaluation
• Approximation algorithms for a \(k\)-line center
• scientific article; zbMATH DE number 7278055
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Approximating k-center in planar graphs
• scientific article; zbMATH DE number 1947381

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A constant approximation for colorful k-center
• A Lottery Model for Center-Type Problems With Outliers
• Algorithms for facility location problems with outliers. (Extended abstract)
• Analytical approach to parallel repetition
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
• Clustering to minimize the maximum intercluster distance
• Easy and hard bottleneck location problems
• Fair colorful k-center clustering
• Generalized center problems with outliers
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Improved approximation for tree augmentation: saving by rewiring
• LP-based algorithms for capacitated facility location
• On partial covering for geometric set systems
• On the cost of essentially fair clusterings
• On the existence of subexponential parameterized algorithms
• On uniform capacitated k-median beyond the natural LP relaxation
• Privacy preserving clustering with constraints
• The non-uniform k-center problem

Cited in

(16)

• Fair colorful \(k\)-center clustering
• Approximation algorithms for clustering with dynamic points
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Tight FPT approximation for constrained k-center and k-supplier
• Computing and Combinatorics
• A technique for obtaining true approximations for k-center with covering constraints
• Fair colorful k-center clustering
• A constant approximation for colorful k-center
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• New algorithms for fair \(k\)-center problem with outliers and capacity constraints
• An approximation algorithm for diversity-aware fair \(k\)-supplier problem
• Approximation algorithm for prize-collecting vertex cover with fairness constraints
• Fault-tolerant k-supplier with outliers
• Approximation algorithms for continuous clustering and facility location problems
• Techniques for generalized colorful k-center problems
• Constant FPT approximation algorithms for colorful sum of radii

This page was built for publication: A technique for obtaining true approximations for \(k\)-center with covering constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118113)