On the cost of essentially fair clusterings
From MaRDI portal
Publication:5875470
DOI10.4230/LIPICS.APPROX-RANDOM.2019.18OpenAlexW2978980326MaRDI QIDQ5875470
Daniel R. Schmidt, Martin Groß, Clemens Rösner, Aounon Kumar, Ioana O. Bercea, Melanie Schmidt, Samir Khuller
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1811.10319
Related Items (9)
Efficient algorithms for fair clustering with a new notion of fairness ⋮ Attraction-repulsion clustering: a way of promoting diversity linked to demographic parity in fair clustering ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ New algorithms for fair \(k\)-center problem with outliers and capacity constraints ⋮ Tight FPT approximation for socially fair clustering ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Algorithms for fair \(k\)-clustering with multiple protected attributes ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- Improved and simplified inapproximability for \(k\)-means
- Clustering to minimize the maximum intercluster distance
- Easy and hard bottleneck location problems
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Fair coresets and streaming algorithms for fair \(k\)-means
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Approximating $k$-Median via Pseudo-Approximation
- Fairness through awareness
- Improved Approximation Guarantees for Lower-Bounded Facility Location
- A 5-Approximation for Capacitated Facility Location
- Achieving anonymity via clustering
- Lower-bounded facility location
- Constant Factor Approximation for Capacitated k-Center with Outliers
- LP-Based Algorithms for Capacitated Facility Location
- An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
- Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
- A new greedy approach for facility location problems
- Clustering with Diversity
- Greedy Strikes Back: Improved Facility Location Algorithms
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- Approximating capacitated k-median with (1 + ∊)k open facilities
- Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
- Constant approximation for k-median and k-means with outliers via iterative rounding
This page was built for publication: On the cost of essentially fair clusterings
