Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
From MaRDI portal
Publication:3467834
DOI10.1007/978-3-319-26626-8_5zbMath1478.90113MaRDI QIDQ3467834
Yishui Wang, Chen-Chen Wu, Da-Chuan Xu, Dong-lei Du
Publication date: 5 February 2016
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_5
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
90B80: Discrete location and assignment
Related Items
An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme, An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
Cites Work
- Unnamed Item
- A survey on offline scheduling with rejection
- A note on the prize collecting traveling salesman problem
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- A new approximation algorithm for the \(k\)-facility location problem
- A constant-factor approximation algorithm for the k -median problem (extended abstract)
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Local Search Heuristics for k-Median and Facility Location Problems
- Multiprocessor Scheduling with Rejection
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization