M^pUFLP: universal facility location problem in the p-th power of metric space

DOI10.1016/J.TCS.2020.05.038MaRDI QIDQ2197535zbMATH OpenOpenAlexFDO

Authors Yicheng Xu, Yong Zhang, Juan Zou, Dachuan Xu

Publication date 1 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.05.038

zbMATH Keywords

\(p\)-th power metricapproximation algorithmfacility locationsquared metricuniversal facility location

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Algorithms - ESA 2003
• Improved local search for universal facility location
• Improved local search for universal facility location
• Improved approximation for universal facility location
• A local search approximation algorithm for a squared metric \(k\)-facility location problem

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 5-approximation for capacitated facility location
• A 5-approximation for universal facility location
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Algorithms - ESA 2003
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation hardness of Travelling Salesman via weighted amplifiers
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• From stars to comets: improved local search for universal facility location
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• Improved approximation algorithm for universal facility location problem with linear penalties
• Local search algorithm for universal facility location problem with linear penalties
• LP-based algorithms for capacitated facility location
• Network flows. Theory, algorithms, and applications.

Cited in

(5)

• Approximating the \(\tau\)-relaxed soft capacitated facility location problem
• Improved approximation algorithms for solving the squared metric k-facility location problem
• Universal facility location in generalized metric space
• Approximate the lower-bounded connected facility location problem
• Approximation algorithms for the individually fair k-center with outliers

This page was built for publication: \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197535)