Back to Search
Start Over
A Technique for Obtaining True Approximations for k-Center with Covering Constraints
- Source :
- Mathematical Programming, Mathematical Programming, 192 (1), Lecture Notes in Computer Science, Lecture Notes in Computer Science-Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 12125, Integer Programming and Combinatorial Optimization, Integer Programming and Combinatorial Optimization ISBN: 9783030457709, IPCO, Integer Programming and Combinatorial Optimization-21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings
- Publication Year :
- 2022
-
Abstract
- There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P≠NP. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.<br />Mathematical Programming, 192 (1)<br />ISSN:0025-5610<br />ISSN:1436-4646
- Subjects :
- FOS: Computer and information sciences
050101 languages & linguistics
Mathematical optimization
Theoretical computer science
Computer science
General Mathematics
Polyhedral techniques
0102 computer and information sciences
02 engineering and technology
010501 environmental sciences
01 natural sciences
Clustering
Lottery
Computer Science - Data Structures and Algorithms
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
0501 psychology and cognitive sciences
Center (algebra and category theory)
Approximation algorithms
k-Center
Cluster analysis
Mathematics - Optimization and Control
0105 earth and related environmental sciences
Mathematics
Numerical analysis
05 social sciences
Approximation algorithm
90C27, 68W40, 68Q25, 90C05
010201 computation theory & mathematics
Optimization and Control (math.OC)
020201 artificial intelligence & image processing
Software
Subjects
Details
- ISBN :
- 978-3-030-45770-9
978-3-030-45771-6 - ISSN :
- 00255610, 14364646, 03029743, and 16113349
- ISBNs :
- 9783030457709 and 9783030457716
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....14e243040fcf92034c8cca11f788e3d9
- Full Text :
- https://doi.org/10.1007/s10107-021-01645-y