Cover Image

A QPTAS for Facility Location on Unit Disk graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Friggstad, Zachary, Rezapour, Mohsen, Salavatipour, Mohammad R., Sun, Hao
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
by: Friggstad, Zachary, et al.
Published: (2018)

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

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

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
by: Ghaseminia, Benyamin, et al.
Published: (2025)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

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

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

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

Facility Location on High-dimensional Euclidean Spaces
by: Lee, Euiwoong, et al.
Published: (2025)

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

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

Dynamic Unit-Disk Range Reporting
by: Wang, Haitao, et al.
Published: (2024)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

Computing Maximum Cliques in Unit Disk Graphs
by: Tkachenko, Anastasiia, et al.
Published: (2025)

Improved Lower Bound for Differentially Private Facility Location
by: Manurangsi, Pasin
Published: (2024)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

On the Line-Separable Unit-Disk Coverage and Related Problems
by: Liu, Gang, et al.
Published: (2023)

Compatibility of Max and Sum Objectives for Committee Selection and $k$-Facility Location
by: Han, Yue, et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
by: Liu, Gang, et al.
Published: (2024)

Subcoloring of (Unit) Disk Graphs
by: Marin, Malory, et al.
Published: (2025)

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

Strategic Facility Location via Predictions
by: Chen, Qingyun, et al.
Published: (2024)

Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
by: Fish, Sara, et al.
Published: (2026)

Online Facility Assignments on Polygons
by: Malik, Sumaiya, et al.
Published: (2025)

Location-Restricted Stable Matching
by: Castro, Garret
Published: (2025)

The trace reconstruction problem for spider graphs
by: Sun, Alec, et al.
Published: (2022)

Servicing Matched Client Pairs with Facilities
by: Abbasi, Fateme, et al.
Published: (2026)

HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
by: Dehghankar, Mohsen, et al.
Published: (2025)

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
by: Ghaffari, Mohsen, et al.
Published: (2024)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
by: Ghaffari, Mohsen, et al.
Published: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)