Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Fair Colorful k-Center Clustering
 
conference paper

Fair Colorful k-Center Clustering

Jia, Xinrui  
•
Sheth, Kshiteej
•
Svensson, Ola Nils Anders  
Bienstock D., Zambelli G.
April 14, 2020
Integer Programming and Combinatorial Optimization. IPCO 2020
21st International Conference Integer Programming and Combinatorial Optimization (IPCO)

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-030-45771-6_17
Author(s)
Jia, Xinrui  
Sheth, Kshiteej
Svensson, Ola Nils Anders  
Editors
Bienstock D., Zambelli G.
Date Issued

2020-04-14

Publisher

Springer

Publisher place

Cham

Published in
Integer Programming and Combinatorial Optimization. IPCO 2020
ISBN of the book

978-3-030-45770-9

Series title/Series vol.

Lecture Notes in Computer Science; 12125

Volume

12125

Start page

209

End page

222

Subjects

Approximation algorithms

•

k-Center Clustering and facility location

•

Fairness

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Event nameEvent placeEvent date
21st International Conference Integer Programming and Combinatorial Optimization (IPCO)

London, UK

June 8-10, 2020

RelationURL/DOI

IsSourceOf

https://infoscience.epfl.ch/record/287277
Available on Infoscience
June 14, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/169287
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés