A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
- 10 May 2011
- journal article
- Published by Springer Nature in Algorithmica
- Vol. 63 (1-2) , 191-200
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2010
- An approximation algorithm for the k-level capacitated facility location problemJournal of Combinatorial Optimization, 2009
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location ProblemSIAM Journal on Discrete Mathematics, 2004
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- A push-relabel framework for submodular function minimization and applications to parametric optimizationDiscrete Applied Mathematics, 2003
- Improved combinatorial algorithms for the facility location and k-median problems2003
- Improved Approximation Algorithms for the Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2003
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- A 3-approximation algorithm for the -level uncapacitated facility location problemInformation Processing Letters, 1999
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999