:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Lee, Euiwoong, Shin, Kijun
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2501.18105
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Learning Augmented Graph $k$-Clustering
by: Fan, Chenglin, et al.
Published: (2025)

SVD Provably Denoises Nearest Neighbor Data
by: Kannan, Ravindran, et al.
Published: (2026)

Separating $k$-Median from the Supplier Version
by: Anand, Aditya, et al.
Published: (2024)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
by: Lee, Dahoon, et al.
Published: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

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

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

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

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

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

Unbreakable Decomposition in Close-to-Linear Time
by: Anand, Aditya, et al.
Published: (2024)

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

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

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

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

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

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

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
by: Moretti, Simone, et al.
Published: (2022)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

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

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

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
by: Ahn, Jungho, et al.
Published: (2025)

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

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

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

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
by: Deng, Chengyuan, et al.
Published: (2025)