Cover Image

Logarithmic Approximations for Fair k-Set Selection

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Shi, Xu, Chenyang, Zhang, Ruilong
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

Fair Submodular Maximization over a Knapsack Constraint
by: Li, Lijun, et al.
Published: (2025)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
by: Ma, Qingwen, et al.
Published: (2026)

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

FPT Approximations for Fair $k$-Min-Sum-Radii
by: Carta, Lena, et al.
Published: (2024)

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

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
by: Feng, Yuda, et al.
Published: (2024)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

Fair Set Cover
by: Dehghankar, Mohsen, et al.
Published: (2024)

Public Event Scheduling with Busy Agents
by: Li, Bo, et al.
Published: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Approximation Algorithms for Fair Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2025)

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

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

On Fair Epsilon Net and Geometric Hitting Set
by: Dehghankar, Mohsen, et al.
Published: (2025)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
by: Chakraborty, Diptarka, et al.
Published: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

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

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

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
by: Bhangale, Amey, et al.
Published: (2026)

Dynamic Treewidth in Logarithmic Time
by: Korhonen, Tuukka
Published: (2025)

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

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

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

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
by: Dey, Dipan, et al.
Published: (2025)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
by: Liu, Yang P., et al.
Published: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
by: Dumitrescu, Adrian
Published: (2021)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
by: Manurangsi, Pasin
Published: (2024)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
by: Li, Shi
Published: (2024)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)