Buchumschlag

On the Hardness of Approximation of the Fair k-Center Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Thejaswi, Suhas
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
von: Thejaswi, Suhas, et al.
Veröffentlicht: (2024)

Hardness of Maximum Likelihood Learning of DPPs
von: Grigorescu, Elena, et al.
Veröffentlicht: (2022)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

A Note on Approximability of Densest At-Least-k-Subgraph
von: Laekhanukit, Bundit, et al.
Veröffentlicht: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
von: Lee, Euiwoong, et al.
Veröffentlicht: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Generalizing Fair Top-$k$ Selection: An Integrative Approach
von: Cai, Guangya
Veröffentlicht: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
von: Funk, Nicole, et al.
Veröffentlicht: (2026)

Hardness of Median and Center in the Ulam Metric
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
von: Bhaskar, Umang, et al.
Veröffentlicht: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Training Neural Networks is NP-Hard in Fixed Dimension
von: Froese, Vincent, et al.
Veröffentlicht: (2023)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
von: Sato, Atsuki, et al.
Veröffentlicht: (2025)

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Samplability makes learning easier
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Efficient Turing Machine Simulation with Transformers
von: Li, Qian, et al.
Veröffentlicht: (2025)

Is nasty noise actually harder than malicious noise?
von: Blanc, Guy, et al.
Veröffentlicht: (2025)