The power of priority algorithms for facility location and set cover

DOI10.1007/s00453-004-1113-2zbMath1108.68126OpenAlexW2132274124MaRDI QIDQ1884771

Spyros Angelopoulos, Allan Borodin

Publication date: 5 November 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1113-2

zbMATH Keywords

greedy algorithmfacility locationset coverapproximation lower bound

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Related Items

Models of greedy algorithms for graph problems, Advice complexity of adaptive priority algorithms, Toward a model for backtracking and dynamic programming, Limitations of incremental dynamic programming, On exponential time lower bound of Knapsack under backtracking, A stronger model of dynamic programming algorithms, Randomized priority algorithms, Advice complexity of priority algorithms, Priority algorithms for the subset-sum problem