Facility location, distributed approximation. (English) Zbl 1314.68386
Proceedings of the 24th annual ACM symposium on principles of distributed computing, PODC ’05, Las Vegas, NV, USA, July 17–20, 2005. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-994-2). 108-117 (2005).
MSC:
| 68W15 | Distributed algorithms |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W25 | Approximation algorithms |
| 90B85 | Continuous location |
| 90C05 | Linear programming |
References:
| [1] | B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM, 32(4):804-823, 1985. 10.1145/4221.4227 · Zbl 0628.68045 |
| [2] | M. L. Balinski. On Finding Integer Solutions to Linear Programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pages 225-248, 1966. |
| [3] | Y. Bartal, J. W. Byers, and D. Raz. Global Optimization Using Local Information with Applications to Flow Control. In Proc. 38th Symposium on Foundations of Computer Science (FOCS), pages 303-312, 1997. |
| [4] | G. Cornuejols, G. Nemhauser, and L. Wolsey. Discrete Location Theory, chapter The Uncapacitated Facility Location Problem, pages 119-171. Wiley, 1990. · Zbl 0727.90043 |
| [5] | M. Elkin. An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem. In Proceedings of the 36th annual ACM Symposium on Theory of Computing (STOC), pages 331-340, 2004. 10.1145/1007352.1007407 · Zbl 1192.68319 |
| [6] | M. Elkin. Distributed Approximation - A Survey. ACM SIGACT News - Distributed Computing Column, 35(4), 2004. 10.1145/1054916.1054931 |
| [7] | U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, 45(4):634-652, 1998. 10.1145/285055.285059 · Zbl 1065.68573 |
| [8] | M. X. Goemans and D. P. Williamson. A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput., 24(2):296-317, 1995. 10.1137/S0097539793242618 · Zbl 0834.68055 |
| [9] | M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The Facility Location Problem with General Cost Functions. Networks, 42(1):42-47, 2003. · Zbl 1032.90015 |
| [10] | W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proc. 33rd Hawaii International Conference on System Sciences (HICSS), page 8020, 2000. |
| [11] | D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148-162, 1982. · Zbl 0473.90029 |
| [12] | K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. Greedy Facility Location Algorithms analyzed using Dual Fitting with Factor-Revealing LP. Journal of the ACM, 50(6):795-824, 2003. 10.1145/950620.950621 · Zbl 1325.90060 |
| [13] | K. Jain and V. V. Vazirani. Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 1999. |
| [14] | M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a Local Search Heuristic for Facility Location Problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-10. Society for Industrial and Applied Mathematics, 1998. · Zbl 0922.90100 |
| [15] | F. Kuhn, T. Moscibroda, and R. Wattenhofer. Initializing newly deployed ad hoc and sensor networks. In Proceedings of 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 260-274, 2004. 10.1145/1023720.1023746 |
| [16] | F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot be Computed Locally! In Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC), pages 300-309, 2004. 10.1145/1011767.1011811 · Zbl 1321.68478 |
| [17] | F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC), pages 25-32, 2003. 10.1145/872035.872040 · Zbl 1321.68479 |
| [18] | J.-H. Lin and J. S. Vitter. ε-Approximations with Minimum Packing Constraint Violation. In Proceedings of the 24th ACM Symposium on Theory of Computing (STOC), pages 771-782, 1992. 10.1145/129712.129787 |
| [19] | N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. 10.1137/0221015 · Zbl 0787.05058 |
| [20] | Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg. MST Construction in O(log log n) Communication Rounds. In Proceedings of the 15th ACM symposium on Parallel Algorithms and Architectures (SPAA), pages 94-100. ACM Press, 2003. 10.1145/777412.777428 |
| [21] | M. Luby and N. Nisan. A Parallel Approximation Algorithm for Positive Linear Programming. In Proc. of the 25th ACM Symposium on Theory of Computing (STOC), pages 448-457, 1993. 10.1145/167088.167211 · Zbl 1310.68224 |
| [22] | C. Lund and M. Yannakakis. On the Hardness of Approximating Minimization Problems. Journal of the ACM, 41(5). 10.1145/185675.306789 · Zbl 0814.68064 |
| [23] | C. Papadimitriou and M. Yannakakis. Linear Programming Without the Matrix. In Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pages 121-129. ACM Press, 1993. 10.1145/167088.167127 · Zbl 1310.90073 |
| [24] | D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000. · Zbl 0959.68042 |
| [25] | D. Peleg and V. Rubinovich. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput., 30(5):1427-1442, 2001. 10.1137/S0097539700369740 · Zbl 0973.05074 |
| [26] | S. Rajagopalan and V. Vazirani. Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. SIAM Journal on Computing, 28:525-540, 1998. 10.1137/S0097539793260763 · Zbl 0914.68096 |
| [27] | D. B. Shmoys, E. Tardos, and K. I. Aardal. Approximation Algorithms for Facility Location Problems. In Proc. 29th Symposium on Theory of Computing (STOC), pages 265-274, 1997. 10.1145/258533.258600 · Zbl 0962.68008 |
| [28] | C. Swamy and D. B. Shmoys. Fault-Tolerant Facility Location. In Proc. 14th Symposium on Discrete Algorithms (SODA), pages 735-736, 2003. · Zbl 1092.68737 |
| [29] | D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. In Proc. 25th Symposium on Theory of Computing (STOC), pages 708-717, 1993. 10.1145/167088.167268 · Zbl 1310.90116 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
