Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties

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

zbMATH Keywords

approximation algorithm; local search; penalty; \(k\)-median; \(k\)-facility location

Mathematics Subject Classification ID

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