Copertina

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bandyapadhyay, Sayan, Chlamtáč, Eden, Friggstad, Zachary, Jamshidian, Mahya, Makarychev, Yury, Vakilian, Ali
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Artificial Intelligence Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
di: Friggstad, Zachary, et al.
Pubblicazione: (2024)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
di: Nezhad, Sina Bagheri, et al.
Pubblicazione: (2025)

Max-Cut with Multiple Cardinality Constraints
di: Makarychev, Yury, et al.
Pubblicazione: (2025)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
di: Makarychev, Yury
Pubblicazione: (2026)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2023)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
di: Friggstad, Zachary, et al.
Pubblicazione: (2025)

Scalable Algorithms for Individual Preference Stable Clustering
di: Mosenzon, Ron, et al.
Pubblicazione: (2024)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
di: la Tour, Max Dupré, et al.
Pubblicazione: (2024)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
di: DeHaan, Ian, et al.
Pubblicazione: (2024)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2026)

Hardness of Approximation for Shortest Path with Vector Costs
di: Carlson, Charlie, et al.
Pubblicazione: (2025)

Constraint Satisfaction Problems with Advice
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2024)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
di: Makarychev, Yury, et al.
Pubblicazione: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Approximating Traveling Salesman Problems Using a Bridge Lemma
di: Böhm, Martin, et al.
Pubblicazione: (2024)

Extraction Theorems With Small Extraction Numbers
di: Agarwal, Arjun, et al.
Pubblicazione: (2024)

Deterministic $k$-Median Clustering in Near-Optimal Time
di: Costa, Martín, et al.
Pubblicazione: (2025)

Facility Location and $k$-Median with Fair Outliers
di: Dabas, Rajni, et al.
Pubblicazione: (2025)

Learning-Based Algorithms for Graph Searching Problems
di: DePavia, Adela Frances, et al.
Pubblicazione: (2024)

Polynomial-Time Approximability of Constrained Reinforcement Learning
di: McMahan, Jeremy
Pubblicazione: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
di: Dong, Yinhao, et al.
Pubblicazione: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
di: Song, Zhao, et al.
Pubblicazione: (2024)

Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All
di: Panda, Atasi, et al.
Pubblicazione: (2022)

Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
di: Ganian, Robert, et al.
Pubblicazione: (2025)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
di: Makarychev, Konstantin, et al.
Pubblicazione: (2025)

Limits of Approximating the Median Treatment Effect
di: Addanki, Raghavendra, et al.
Pubblicazione: (2024)

Connected k-Median with Disjoint and Non-disjoint Clusters
di: Eube, Jan, et al.
Pubblicazione: (2025)

Identification for Tree-shaped Structural Causal Models in Polynomial Time
di: Gupta, Aaryan, et al.
Pubblicazione: (2023)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

New and Improved Bounds for Markov Paging
di: Pabbaraju, Chirag, et al.
Pubblicazione: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
di: Fomin, Fedor V., et al.
Pubblicazione: (2024)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2022)

A QPTAS for Facility Location on Unit Disk graphs
di: Friggstad, Zachary, et al.
Pubblicazione: (2024)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
di: Funk, Nicole, et al.
Pubblicazione: (2026)

Average Sensitivity of Hierarchical $k$-Median Clustering
di: Li, Shijie, et al.
Pubblicazione: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
di: Dai, Han, et al.
Pubblicazione: (2025)

Logarithmic Approximations for Fair k-Set Selection
di: Li, Shi, et al.
Pubblicazione: (2025)