Approximation Algorithms for Bounded Facility Location Problems

被引：0
作者：
Piotr Krysta
Roberto Solis-Oba
机构：
[1] Max-Planck-Institut für Informatik,
来源：
Journal of Combinatorial Optimization | 2001年 / 5卷
关键词：
facility location; approximation algorithms; randomized algorithms; clustering;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v ∈ V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.
引用
收藏
页码：233 / 247
页数：14
相关论文
共 50 条
[41]   Approximation Algorithms for Capacitated Location Routing [J].
Harks, Tobias ;
Koenig, Felix G. ;
Matuschke, Jannik .
TRANSPORTATION SCIENCE, 2013, 47 (01) :3-22
[42]   Lower-Bounded Facility Location [J].
Svitkina, Zoya .
ACM TRANSACTIONS ON ALGORITHMS, 2010, 6 (04)
[43]   Heuristic algorithms for general k-level facility location problems [J].
Li, R. ;
Huang, H-C ;
Huang, J. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2013, 64 (01) :106-113
[44]   APPROXIMATION ALGORITHMS FOR FAULT TOLERANT FACILITY ALLOCATION [J].
Shen, Hong ;
Xu, Shihong .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (03) :1584-1609
[45]   Covering problems in facility location: A review [J].
Farahani, Reza Zanjirani ;
Asgari, Nasrin ;
Heidari, Nooshin ;
Hosseininia, Mahtab ;
Goh, Mark .
COMPUTERS & INDUSTRIAL ENGINEERING, 2012, 62 (01) :368-407
[46]   Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].
Jain, K ;
Vazirani, VV .
JOURNAL OF THE ACM, 2001, 48 (02) :274-296
[47]   An approximation algorithm for the maximization version of the two level uncapacitated facility location problem [J].
Bumb, A .
OPERATIONS RESEARCH LETTERS, 2001, 29 (04) :155-161
[48]   Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams [J].
Marx, Daniel ;
Pilipczuk, Michal .
ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (02)
[49]   Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees [J].
Binay Bhattacharya ;
Qiaosheng Shi ;
Arie Tamir .
Algorithmica, 2009, 55 :601-618
[50]   Minimizing Movement in Mobile Facility Location Problems [J].
Friggstad, Zachary ;
Salavatipour, Mohammad R. .
ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (03)
12345