Cover Image

An improved approximation algorithm for k-Median

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Young, Neal E.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms 68W25 (Primary) 90-08, 90B80, 90C10, 90C05 (Secondary) F.2.1; G.1.6; G.2.2; G.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
by: Li, Shisheng
Published: (2026)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
by: Emmerich, Michael T. M.
Published: (2026)

Extended Dijkstra algorithm and Moore-Bellman-Ford algorithm
by: Cheng, Cong-Dian
Published: (2017)

Modern column generation for estimating single- and multi-purchase ranked list choice models
by: Costa, Luciano, et al.
Published: (2026)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
by: Foos, Josefine, et al.
Published: (2023)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
by: Ali, Alejandro Mata
Published: (2025)

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination
by: Fang, Xiaolei, et al.
Published: (2026)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

A simple algorithm for the simple bilevel programming (SBP) problem
by: Dempe, Stephan, et al.
Published: (2025)

Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network
by: Banerjee, Santanu, et al.
Published: (2025)

A unified worst case for classical simplex and policy iteration pivot rules
by: Disser, Yann, et al.
Published: (2023)

Polyhedral approach to weighted connected matchings in general graphs
by: Samer, Phillippe, et al.
Published: (2023)

Asymmetry in the Complexity of the Multi-Commodity Network Pricing Problem
by: Bui, Quang Minh, et al.
Published: (2022)

Convex Mixed-Integer Nonlinear Programs Derived from Generalized Disjunctive Programming using Cones
by: Neira, David E. Bernal, et al.
Published: (2021)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

Quantitative Indicators for Strength of Inequalities with Respect to a Polyhedron, Part I: Theory
by: Warme, David M.
Published: (2024)

Quantitative Indicators for Strength of Inequalities with Respect to a Polyhedron, Part II: Applications and Computational Evidence
by: Warme, David M.
Published: (2024)

Compressed and Sparse Models for Non-Convex Decentralized Learning
by: Campbell, Andrew, et al.
Published: (2023)

Nonlinear PageRank Problem for Local Graph Partitioning
by: Kodsi, Costy, et al.
Published: (2024)

Hybrid LLM and Higher-Order Quantum Approximate Optimization for CSA Collateral Management
by: Jin, Tao, et al.
Published: (2025)

PRIME: Efficient Algorithm for Token Graph Routing Problem
by: Xu, Haotian, et al.
Published: (2026)

Designing Capacitated Subnetworks for Shortest Path Routing
by: Chimani, Markus, et al.
Published: (2026)

Gradient Descent Methods for Regularized Optimization
by: Nikolovski, Filip, et al.
Published: (2024)

Decentralized Optimization in Networks with Arbitrary Delays
by: Ortega, Tomas, et al.
Published: (2024)

Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs
by: Ju, Caleb, et al.
Published: (2023)

A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
by: Ryabchenko, Alexander, et al.
Published: (2026)

From approximate to exact integer programming
by: Dadush, Daniel, et al.
Published: (2022)