nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.05.2014

A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design

verfasst von: Peng Zhang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio \(O(\sqrt{q})\), where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log² n)), our approximation ratio \(O(\sqrt{q})\) is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.

Vorheriger Artikel Hardness results and approximation algorithm for total liar’s domination in graphs

Nächster Artikel Bandwidth sums of block graphs and cacti

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Andrews M (2004) Hardness of buy-at-bulk network design. In: Proceedings of the 45th symposium on foundations of computer science (FOCS), pp 115–124 CrossRef

Andrews M, Zhang L (1998) The access network design problem. In: Proceedings of the 39th annual symposium on foundations of computer science (FOCS), pp 40–59

Awerbuch B, Azar Y (1997) Buy-at-bulk network design. In: Proceedings of the 38th annual IEEE symposium on foundations of computer science (FOCS), pp 542–547 CrossRef

Bartal Y (1996) Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th annual symposium on foundations of computer science (FOCS), pp 184–193

Bartal Y (1998) On approximating arbitrary metrics by tree metrics. In: Proceedings of the 30th annual ACM symposium on theory of computing (STOC), pp 161–168

Charikar M, Chekuri C, Goel A, Guha S, Plotkin SA (1998) Approximating a finite metric by a small number of tree metrics. In: Proceedings of the 39th annual symposium on foundations of computer science (FOCS), pp 379–388

Charikar M, Karagiozova A (2005) On non-uniform multicommodity buy-at-bulk network design. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC), pp 176–182

Chekuri C, Hajiaghayi M, Kortsarz G, Salavatipour M (2010) Approximation algorithms for nonuniform buy-at-bulk network design. SIAM J Comput 39(5):1772–1798 CrossRefMATHMathSciNet

Chlebík M Chlebíková J (2002) Approximation hardness of the Steiner tree problem on graphs. In: Penttonen M, Schmidt E (eds) Proceedings of the 8th Scandinavian workshop on algorithm theory (SWAT), pp 170–179

Chudak FA, Roughgarden T, Williamson DP (2004) Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Math Program 100(2):411–421 CrossRefMATHMathSciNet

Chuzhoy J, Gupta A, Naor J, Sinha A (2008) On the approximability of some network design problems. ACM Trans Algorithms 4(2):23 CrossRefMathSciNet

Eisenbrand F, Grandoni F, Oriolo G, Skutella M (2007) New approaches for virtual private network design. SIAM J Comput 37(3):706–721 CrossRefMATHMathSciNet

Eisenbrand F, Grandoni F, RothvoßT, Schäfer G (2010) Connected facility location via random facility sampling and core detouring. J Comput Syst Sci 76(8):709–726 CrossRefMATH

Fakcharoenphol J, Rao S, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69(3):485–497 CrossRefMATHMathSciNet

Garey M, Johnson D (1979) Computers and intractability. Freeman, New York MATH

Garg N (2005) Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC), pp 396–402

Garg N, Khandekar R, Konjevod G, Ravi R, Salman FS, Sinha A (2001) On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In: Aardal K, Gerards B (eds) Proceedings of the 8th international conference on integer programming and combinatorial optimization (IPCO). LNCS, vol 2081. Springer, Heidelberg, pp 170–184 CrossRef

Grandoni F, Italiano G (2006) Improved approximation for single-sink buy-at-bulk. In: Asano T (ed) Proceedings of the 17th international symposium on algorithms and computation (ISAAC). LNCS, vol 4288. Springer, Heidelberg, pp 111–120

Grandoni F, RothvoßT (2010) Network design via core detouring for problems without a core. In: Abramsky S, Gavoille C, Kirchner C, Friedhelm Meyer auf der Heide, Spirakis PG (eds) Proceedings of the 37th international colloquium on automata, languages and programming (ICALP). LNCS, vol 6198. Springer, Heidelberg, pp 490–502 CrossRef

Guha S, Meyerson A, Munagala K (2001) A constant factor approximation for the single sink edge installation problems. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC), pp 383–388

Gupta A, Kumar A, Kleinberg J, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC), pp 389–398

Gupta A, Kumar A, Roughgarden T (2003) Simpler and better approximation algorithms for network design. In: Proceedings of the 35th ACM symposium on theory of computing (STOC), pp 365–372

Gupta A, Kumar A, Pál M, Roughgarden T (2007) Approximation via cost sharing: simpler and better approximation algorithms for network design. J ACM 54(3):11 CrossRefMATHMathSciNet

Hajiaghayi M, Jain K (2006) The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 631–640

Jothi R, Raghavachari B (2004) Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Hagerup T, Katajainen J (eds) Proceedings of SWAT. LNCS, vol 3111, pp 336–348

Karger DR, Minkoff M (2000) Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st annual IEEE symposium on foundations of computer science (FOCS), pp 613–623

Kumar A, Gupta A, Roughgarden T (2002) A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the 43rd annual IEEE symposium on foundations of computer science (FOCS), pp 333–342

Meyerson A, Munagala K, Plotkin S (2000) Cost-distance: two metric network design. In: Proceedings of the 41st annual IEEE symposium on foundations of computer science (FOCS), pp 624–630

Ravi R, Sundaram R, Marathe MV, Rosenkrantz DJ, Ravi SS (1994) Spanning trees short or small. In: Proceedings of the 5th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 546–555

Salman F, Cheriyan J, Ravi R, Subramanian S (1997) Buy-at-bulk network design: approximating the single-sink edge installation problem. In: Proceedings of the 8th ACM-SIAM symposium on discrete algorithms (SODA), pp 619–628

Talwar K (2002) Single-sink buy-at-bulk LP has constant integrality gap. In: Cook W, Schulz AS (eds) Proceedings of the 9th conference on integer programming and combinatorial optimization (IPCO). LNCS, vol 2337. Springer, Heidelberg, pp 475–486 CrossRef

Zhang P (2011) A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design. In: Wang W-F, Zhu X-D, Du D-Z (eds) Proceedings of the 5th annual international conference on combinatorial optimization and applications (COCOA). LNCS, vol 6831, pp 525–536 CrossRef

Zhang P, Zhu D, Luan J (2012) An approximation algorithm for the generalized k-multicut problem. Discrete Appl Math 160(7-8):1240–1247 CrossRefMATHMathSciNet

van Zuylen A (2011) Deterministic sampling algorithms for network design. Algorithmica 60(1):110–151 CrossRefMATHMathSciNet

Titel: A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design
verfasst von: Peng Zhang
Publikationsdatum: 01.05.2014
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9544-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2014

Paired versus double domination in K 1,r -free graphs

Linear time-dependent constraints programming with MSVL

Solving the Multidimensional Assignment Problem by a Cross-Entropy method

Multiple L(j,1)-labeling of the triangular lattice

Bandwidth sums of block graphs and cacti

Hardness results and approximation algorithm for total liar’s domination in graphs

Premium Partner