Fair Colorful k-Center Clustering

DOI10.1007/978-3-030-45771-6_17zbMath1503.90110arXiv2007.04059OpenAlexW3104789887MaRDI QIDQ5041747

Kshiteej Sheth, Xinrui Jia, Ola Svensson

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.04059

zbMATH Keywords

fairnessapproximation algorithms\(k\)-centerclustering and facility location

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Approximation algorithms for clustering with dynamic points ⋮ On fair covering and hitting problems ⋮ Efficient algorithms for fair clustering with a new notion of fairness ⋮ On colorful vertex and edge cover problems ⋮ Groups burning: analyzing spreading processes in community-based networks ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ Robust \(k\)-center with two types of radii ⋮ Robust \(k\)-center with two types of radii ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering to minimize the maximum intercluster distance
• Easy and hard bottleneck location problems
• Global Optimization with Polynomials and the Problem of Moments
• Lift-and-Project Methods for Set Cover and Knapsack
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• New Tools for Graph Coloring
• A Best Possible Heuristic for the k-Center Problem
• A Lottery Model for Center-Type Problems With Outliers
• CSP gaps and reductions in the lasserre hierarchy
• Complexity of Positivstellensatz proofs for the knapsack