The traveling \(k\)-median problem: approximating optimal network coverage

DOI10.1007/978-3-030-92702-8_6OpenAlexW4205472357MaRDI QIDQ2085738

Guido Schäfer, Dylan Huizing

Publication date: 19 October 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92702-8_6

zbMATH Keywords

approximation algorithms\(k\)-median problemnetwork coveragerouting over time

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• The \(k\)-server problem
• Relocation-promotion problem with Euclidean distance
• A Langrangean heuristic for the \(p_ k\)-median dynamic location problem
• The median routing problem for simultaneous planning of emergency response and non-emergency jobs
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning
• The maximal expected coverage relocation problem for emergency vehicles
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Greedy Strikes Back: Improved Facility Location Algorithms
• An optimal on-line algorithm for metrical task system
• On the k -server conjecture
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles
• A dynamic model and parallel tabu search heuristic for real-time ambulance relocation