nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

20. Network Design Problems

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Connectivity is a very important concept in combinatorial optimization. In Chapter 8 we showed how to compute the connectivity between each pair of vertices of an undirected graph. Now we are looking for subgraphs that satisfy certain connectivity requirements.

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 "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

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

Vorheriges Kapitel Multicommodity Flows and Edge-Disjoint Paths

Nächstes Kapitel The Traveling Salesman Problem

Cheng, X., and Du, D.-Z. [2001]: Steiner Trees in Industry. Kluwer, Dordrecht 2001

Du, D.-Z., Smith, J.M., and Rubinstein, J.H. [2000]: Advances in Steiner Trees. Kluwer, Boston 2000

Goemans, M.X., and Williamson, D.P. [1996]: The primal-dual method for approximation algorithms and its application to network design problems. In: Approximation Algorithms for NP-Hard Problems. (D.S. Hochbaum, ed.), PWS, Boston, 1996

Grötschel, M., Monma, C.L., and Stoer, M. [1995]: Design of survivable networks. In: Handbooks in Operations Research and Management Science; Volume 7; Network Models (M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser, eds.), Elsevier, Amsterdam 1995

Gupta, A., and Könemann, J. [2011]: Approximation algorithms for network design: a survey. Surveys in Operations Research and Management Science 16 (2011) 3–20

Hwang, F.K., Richards, D.S., and Winter, P. [1992]: The Steiner Tree Problem; Annals of Discrete Mathematics 53. North-Holland, Amsterdam 1992

Kerivin, H., and Mahjoub, A.R. [2005]: Design of survivable networks: a survey. Networks 46 (2005), 1–21

Lau, L.C., Ravi, R., and Singh, M. [2011]: Iterative Methods in Combinatorial Optimization. Cambridge University Press 2011, Chapter 10

Prömel, H.J., and Steger, A. [2002]: The Steiner Tree Problem. Vieweg, Braunschweig 2002

Stoer, M. [1992]: Design of Survivable Networks. Springer, Berlin 1992

Vazirani, V.V. [2001]: Approximation Algorithms. Springer, Berlin 2001, Chapters 22 and 23

Agrawal, A., Klein, P.N., and Ravi, R. [1995]: When trees collide: an approximation algorithm for the generalized Steiner tree problem in networks. SIAM Journal on Computing 24 (1995), 440–456

Arora, S. [1998]: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM 45 (1998), 753–782

Berman, P., and Ramaiyer, V. [1994]: Improved approximations for the Steiner tree problem. Journal of Algorithms 17 (1994), 381–408

Bern, M., and Plassmann, P. [1989]: The Steiner problem with edge lengths 1 and 2. Information Processing Letters 32 (1989), 171–176

Bertsimas, D., and Teo, C. [1995]: From valid inequalities to heuristics: a unified view of primal-dual approximation algorithms in covering problems. Operations Research 46 (1998), 503–514

Bertsimas, D., and Teo, C. [1997]: The parsimonious property of cut covering problems and its applications. Operations Research Letters 21 (1997), 123–132

Björklund, A., Husfeldt, T., Kaski, P., and Koivisto, M. [2007]: Fourier meets Möbius: fast subset convolution. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007), 67–74

Borchers, A., and Du, D.-Z. [1997]: The k-Steiner ratio in graphs. SIAM Journal on Computing 26 (1997), 857–869

Borradaile, G., Klein, P., and Mathieu, C., [2009]: An O(nlogn) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms 5 (2009), Article 31

Byrka, J., Grandoni, F., Rothvoß, T., and Sanità, L. [2013]: Steiner tree approximation via iterative randomized rounding. Journal of the ACM 60 (2013), Article 6

Chakraborty, T., Chuzhoy, J., and Khanna, S. [2008]: Network design for vertex connectivity. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), 167–176

Cheriyan, J., and Vetta, A. [2007]: Approximation algorithms for network design with metric costs. SIAM Journal on Discrete Mathematics 21 (2007), 612–636

Chlebík, M., and Chlebíková, J. [2008]: The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science 406 (2008), 207–214

Choukhmane, E. [1978]: Une heuristique pour le problème de l’arbre de Steiner. RAIRO Recherche Opérationnelle 12 (1978), 207–212 [in French]

Chuzhoy, J., and Khanna, S. [2009]: An O(k ³logn)-approximation algorithm for vertex-connectivity survivable network design. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (2009), 437–441

Dreyfus, S.E., and Wagner, R.A. [1972]: The Steiner problem in graphs. Networks 1 (1972), 195–207

Du, D.-Z., Zhang, Y., and Feng, Q. [1991]: On better heuristic for Euclidean Steiner minimum trees. Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (1991), 431–439. See also Mathematical Programming 57 (1992) 193–202

Erickson, R.E., Monma, C.L., and Veinott, A.F., Jr. [1987]: Send-and-split method for minimum concave-cost network flows. Mathematics of Operations Research 12 (1987), 634–664

Fleischer, L., Jain, K., and Williamson, D.P. [2006]: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences 72 (2006), 838–867

Fuchs, B., Kern, W., Mölle, D., Richter, S., Rossmanith, P., and Wang, X. [2007]: Dynamic programming for minimum Steiner trees. Theory of Computing Systems 41 (2007), 493–500

Gabow, H.N. [2005]: An improved analysis for approximating the smallest k-edge connected spanning subgraph of a multigraph. SIAM Journal on Discrete Mathematics 19 (2005), 1–18

Gabow, H.N., Goemans, M.X., and Williamson, D.P. [1998]: An efficient approximation algorithm for the survivable network design problem. Mathematical Programming B 82 (1998), 13–40

Gabow, H.N., Goemans, M.X., Tardos, É., and Williamson, D.P. [2009]: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53 (2009), 345–357

Garey, M.R., Graham, R.L., and Johnson, D.S. [1977]: The complexity of computing Steiner minimal trees. SIAM Journal of Applied Mathematics 32 (1977), 835–859

Garey, M.R., and Johnson, D.S. [1977]: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics 32 (1977), 826–834

Gilbert, E.N., and Pollak, H.O. [1968]: Steiner minimal trees. SIAM Journal on Applied Mathematics 16 (1968), 1–29

Goemans, M.X., and Bertsimas, D.J. [1993]: Survivable networks, linear programming and the parsimonious property, Mathematical Programming 60 (1993), 145–166

Goemans, M.X., Goldberg, A.V., Plotkin, S., Shmoys, D.B., Tardos, É., and Williamson, D.P. [1994]: Improved approximation algorithms for network design problems. Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994), 223–232

Goemans, M.X., Olver, N., Rothvoß, T., and Zenklusen, R. [2012]: Matroids and integrality gaps for hypergraphic Steiner tree relaxations. Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 1161–1176

Goemans, M.X., and Williamson, D.P. [1995]: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24 (1995), 296–317

Goyal, N., Olver, N., and Shepherd, F.B. [2013]: The VPN conjecture is true. Journal of the ACM 60 (2013), Article 17

Grandoni, F., Kaibel, V., Oriolo, G., and Skutella, M. [2008]: A short proof of the VPN tree routing conjecture on ring networks. Operations Research Letters 36 (2008), 361–365

Gröpl, C., Hougardy, S., Nierhoff, T., and Prömel, H.J. [2001]: Approximation algorithms for the Steiner tree problem in graphs. In: Cheng and Du [2001], pp. 235–279

Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., and Yener, B. [2001]: Provisioning a virtual private network: a network design problem for multicommodity flow. Proceedings of the 33th Annual ACM Symposium on Theory of Computing (2001), 389–398

Hanan, M. [1966]: On Steiner’s problem with rectilinear distance. SIAM Journal on Applied Mathematics 14 (1966), 255–265

Hetzel, A. [1995]: Verdrahtung im VLSI-Design: Spezielle Teilprobleme und ein sequentielles Lösungsverfahren. Ph.D. thesis, University of Bonn, 1995 [in German]

Hougardy, S., and Prömel, H.J. [1999]: A 1. 598 approximation algorithm for the Steiner tree problem in graphs. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (1999), 448–453

Hougardy, S., Silvanus, J., and Vygen, J. [2017]: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Mathematical Programming Computation 9 (2017), 135–202

Hwang, F.K. [1976]: On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics 30 (1976), 104–114

Jain, K. [2001]: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21 (2001), 39–60

Jothi, R., Raghavachari, B., and Varadarajan, S. [2003]: A 5/4-approximation algorithm for minimum 2-edge-connectivity. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003), 725–734

Karp, R.M. [1972]: Reducibility among combinatorial problems. In: Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, eds.), Plenum Press, New York 1972, pp. 85–103

Karpinski, M., and Zelikovsky, A. [1997]: New approximation algorithms for Steiner tree problems. Journal of Combinatorial Optimization 1 (1997), 47–65

Khuller, S., and Raghavachari, B. [1996]: Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms 21 (1996), 434–450

Khuller, S., and Vishkin, U. [1994]: Biconnectivity augmentations and graph carvings. Journal of the ACM 41 (1994), 214–235

Klein, P.N., and Ravi, R. [1993]: When cycles collapse: a general approximation technique for constrained two-connectivity problems. Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference (1993), 39–55

Könemann, J., Olver, N., Pashkovish, K., Ravi, R., Swamy, C., Vygen, J. [2017]: On the integrality gap of the prize-collecting Steiner forest LP. Proceedings of APPROX 2017, Article 17

Korte, B., Prömel, H.J., and Steger, A. [1990]: Steiner trees in VLSI-layout. In: Paths, Flows, and VLSI-Layout (B. Korte, L. Lovász, H.J. Prömel, A. Schrijver, eds.), Springer, Berlin 1990, pp. 185–214

Kortsarz, G., Krauthgamer, R., and Lee, J.R. [2004]: Hardness of approximation for vertex-connectivity network design problems. SIAM Journal on Computing 33 (2004), 704–720

Kou, L.T. [1990]: On efficient implementation of an approximation algorithm for the Steiner tree problem. Acta Informatica 27 (1990), 369–380

Kou, L., Markowsky, G., and Berman, L. [1981]: A fast algorithm for Steiner trees. Acta Informatica 15 (1981), 141–145

Martin, A. [1992]: Packen von Steinerbäumen: Polyedrische Studien und Anwendung. Ph.D. thesis, Technical University of Berlin 1992 [in German]

Mehlhorn, K. [1988]: A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters 27 (1988), 125–128

Melkonian, V., and Tardos, É. [2004]: Algorithms for a network design problem with crossing supermodular demands. Networks 43 (2004), 256–265

Nagarajan, V., Ravi, R., and Singh, M. [2010]: Simpler analysis of LP extreme points for traveling salesman and survivable network design problems. Operations Research Letters 38 (2010), 156–160

Robins, G., and Zelikovsky, A. [2005]: Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics 19 (2005), 122–134

Takahashi, M., and Matsuyama, A. [1980]: An approximate solution for the Steiner problem in graphs. Mathematica Japonica 24 (1980), 573–577

Vygen, J. [2011]: Faster algorithm for optimum Steiner trees. Information Processing Letters 111 (2011), 1075–1079

Warme, D.M., Winter, P., and Zachariasen, M. [2000]: Exact algorithms for plane Steiner tree problems: a computational study. In: Advances in Steiner trees (D.-Z. Du, J.M. Smith, J.H. Rubinstein, eds.), Kluwer Academic Publishers, Boston, 2000, pp. 81–116

Williamson, D.P., Goemans, M.X., Mihail, M., and Vazirani, V.V. [1995]: A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15 (1995), 435–454

Zelikovsky, A.Z. [1993]: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9 (1993), 463–470

Titel: Network Design Problems
verfasst von: Bernhard Korte
Jens Vygen
Verlag: Springer Berlin Heidelberg
Buch: Combinatorial Optimization
Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-662-56039-6_20

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 "Technik"

Springer Professional "Wirtschaft"