Cover Image

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ebbens, Matthijs, Funk, Nicole, Höckendorff, Jan, Sohler, Christian, Weil, Vera
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
by: Park, Seongbin, et al.
Published: (2026)

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

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

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

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

Approximate Algorithms for Chamfer Distance Under Translation
by: Halevi, Gil, et al.
Published: (2026)

Top-k Stabbing Interval Queries
by: Akram, Waseem, et al.
Published: (2024)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
by: Peng, Pan, et al.
Published: (2025)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

Efficient Enumeration of At Most $k$-Out Polygons
by: Akram, Waseem, et al.
Published: (2025)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

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

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

Performance bounds for nearest neighbor search with k-d trees
by: Bazzani, Marco, et al.
Published: (2026)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Minimizing the Size of the Uncertainty Regions for Centers of Moving Entities
by: Evans, William, et al.
Published: (2023)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)