One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk

by Ashish Goel and Ian Post

Theory of Computing, Volume 8(15), pp. 351-368, 2012

Bibliography with links to cited articles

[1]   Matthew Andrews: Hardness of buy-at-bulk network design. In Proc. 45th FOCS, pp. 115–124. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.32]

[2]   Matthew Andrews and Lisa Zhang: The access network design problem. In Proc. 39th FOCS, pp. 40–49. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743427]

[3]   Baruch Awerbuch and Yossi Azar: Buy-at-bulk network design. In Proc. 38th FOCS, pp. 542–547. IEEE Comp. Soc. Press, 1997. [doi:10.1109/SFCS.1997.646143]

[4]   Yair Bartal: Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548477]

[5]   Yair Bartal: On approximating arbitrary metrics by tree metrics. In Proc. 30th STOC, pp. 161–168. ACM Press, 1998. [doi:10.1145/276698.276725]

[6]   Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità: An improved LP-based approximation for Steiner tree. In Proc. 42nd STOC, pp. 583–592. ACM Press, 2010. [doi:10.1145/1806689.1806769]

[7]   Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, and Guido Schäfer: Connected facility location via random facility sampling and core detouring. J. Comput. System Sci., 76(8):709–726, 2010. [doi:10.1016/j.jcss.2010.02.001]

[8]   Mihaela Enachescu, Ashish Goel, Ramesh Govindan, and Rajeev Motwani: Scale-free aggregation in sensor networks. Theoret. Comput. Sci., 344(1):15–29, 2005. Preliminary version in ALGOSENSORS’04. [doi:10.1016/j.tcs.2005.06.023]

[9]   Matthias Englert and Harald Räcke: Oblivious routing for the Lp-norm. In Proc. 50th FOCS, pp. 32–40. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.52]

[10]   Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.04.011]

[11]   Michael L. Fredman and Robert Endre Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596–615, 1987. Preliminary version in FOCS’84. [doi:10.1145/28869.28874]

[12]   Ashish Goel and Deborah Estrin: Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. Algorithmica, 43(1):5–15, 2005. Preliminary version in SODA’03. [doi:10.1007/s00453-005-1155-0]

[13]   Ashish Goel and Ian Post: An oblivious O(1)-approximation for single source buy-at-bulk. In Proc. 50th FOCS, pp. 442–450. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.41]

[14]   Ashish Goel and Ian Post: One tree suffices: A simultaneous O(1)-approximation for single-sink buy-at-bulk. In Proc. 51st FOCS, pp. 593–600. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.62]

[15]   Fabrizio Grandoni and Giuseppe F. Italiano: Improved approximation for single-sink buy-at-bulk. In 17th Int. Symp. on Algorithms and Computation (ISAAC’06), volume 4288, pp. 111–120. Springer, 2006. [doi:10.1007/11940128_13]

[16]   Fabrizio Grandoni and Thomas Rothvoß: Network design via core detouring for problems without a core. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 490–502. Springer, 2010. [doi:10.1007/978-3-642-14165-2_42]

[17]   Sudipto Guha, Adam Meyerson, and Kamesh Munagala: A constant factor approximation for the single sink edge installation problems. In Proc. 33rd STOC, pp. 383–388. ACM Press, 2001. [doi:10.1145/380752.380827]

[18]   Sudipto Guha, Adam Meyerson, and Kamesh Munagala: A constant factor approximation for the single sink edge installation problem. SIAM J. Comput., 38(6):2426–2442, 2010. [doi:10.1137/050643635]

[19]   Anupam Gupta, Mohammad T. Hajiaghayi, and Harald Räcke: Oblivious network design. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 970–979. ACM Press, 2006. [doi:10.1145/1109557.1109665]

[20]   Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, and Bulent Yener: Provisioning a virtual private network: A network design problem for multicommodity flow. In Proc. 33rd STOC, pp. 389–398. ACM Press, 2001. [doi:10.1145/380752.380830]

[21]   Anupam Gupta, Amit Kumar, Martin Pál, and Tim Roughgarden: Approximation via cost sharing: Simpler and better approximation algorithms for network design. J. ACM, 54(3):1–38, 2007. [doi:10.1145/1236457.1236458]

[22]   Anupam Gupta, Aravind Srinivasan, and Éva Tardos: Cost-sharing mechanisms for network design. Algorithmica, 50(1):98–119, 2008. Preliminary version in APPROX’04. [doi:10.1007/s00453-007-9065-y]

[23]   Raja Jothi and Balaji Raghavachari: Improved approximation algorithms for the single-sink buy-at-bulk network design problems. J. Discrete Algorithms, 7(2):249–255, 2009. Preliminary version in SWAT’04. [doi:10.1016/j.jda.2008.12.003]

[24]   David R. Karger and Maria Minkoff: Building Steiner trees with incomplete global knowledge. In Proc. 41st FOCS, pp. 613–623. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892329]

[25]   S. Khuller, B. Raghavachari, and N. Young: Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305–321, 1995. [doi:10.1007/BF01294129]

[26]   Bhaskar Krishnamachari, Deborah Estrin, and Stephen Wicker: Modelling data-centric routing in wireless sensor networks. Technical Report CENG 02-14, Univ. Southern Calif. Dept. EE - Systems (18 pp), 2002. PDF.

[27]   Y. Rabinovich and R. Raz: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom., 19(1):79–94, 1998. [doi:10.1007/PL00009336]

[28]   R. Ravi and F. S. Salman: Approximation algorithms for the traveling purchaser problem and its variants in network design. In Proc. 7th Ann. European Symp. on Algorithms (ESA’99), pp. 696–696. Springer, 1999. [doi:10.1007/3-540-48481-7_4]

[29]   F. S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian: Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’97), pp. 619–628. ACM Press, 1997. [ACM:314397]

[30]   F. S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian: Approximating the single-sink link-installation problem in network design. SIAM J. Optim., 11(3):595–610, 2001. [doi:10.1137/S1052623497321432]

[31]   Chaitanya Swamy and Amit Kumar: Primal-dual algorithms for connected facility location problems. Algorithmica, 40(4):245–269, 2004. Preliminary version in APPROX’02. [doi:10.1007/s00453-004-1112-3]

[32]   Kunal Talwar: The single-sink buy-at-bulk LP has constant integrality gap. In Proc. 9th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’02), pp. 475–486. Springer, 2002. [doi:10.1007/3-540-47867-1_33]

[33]   Anke van Zuylen: Deterministic sampling algorithms for network design. Algorithmica, 60(1):110–151, 2011. Preliminary version in ESA’08. [doi:10.1007/s00453-009-9344-x]

[34]   David P. Williamson and Anke van Zuylen: A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper. Res. Lett., 35(6):702–712, 2007. [doi:10.1016/j.orl.2007.02.005]