Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Unified Approach for Domination Problems on Different Network Topologies Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Dual Integrality in Combinatorial Optimization

verfasst von : Xujin Chen, Xiaodong Hu, Wenan Zang

Erschienen in: Handbook of Combinatorial Optimization

Verlag: Springer New York

Einloggen

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

search-config
loading …

Abstract

The notion of total dual integrality and its variants are powerful tools to derive combinatorial min-max relation efficiently, yielding many fundamental results in combinatorial optimization. Following the pioneering work of Edmonds and Geiles (A min–max relation for submodular functions on graphs, in Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, 1977, pp. 185–204), considerable research efforts have been devoted to the study of the dual integrality from theoretical and algorithmic points of view. This chapter reviews significant progresses that have been made since the publication of Schrijver’s celebrated monograph (Combinatorial Optimization - Polyhedra and Efficiency, Springer, Berlin, 2003), which contained a comprehensive and in-depth treatment of the state-of-the-art in dual integrality theory and its application, among many others.

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 Data Correcting Approach for Routing and Location in Networks
Nächstes Kapitel Dynamical System Approaches to Combinatorial Optimization∗
Literatur
1.
N. Apollonio, Integrality properties of edge path tree families. Discrete Math. 309, 4181–4184 (2009)MathSciNetMATH
2.
M.L. Balinski, Integer programming: methods, uses, computation. Manag. Sci. Ser. A 12, 253–313 (1965)MathSciNetMATH
3.
R. Bar-Yehuda, K. Bendel, A. Freund, D. Rawitz, Local ratio: A unified framework for approximation algorithms. ACM Comput. Surv. 36, 422–463 (2004)
4.
C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1976)MATH
5.
S. Bessy, S. Thomassé, Spanning a strong digraph by \(\alpha\) circuits: A proof of Gallai’s conjecture. Combinatorica 27, 659–667 (2007)MathSciNetMATH
6.
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (Macmillan, London, 1976)MATH
7.
F. Bonomo, G. Durán, M.C. Lin, J.L. Szwarcfiter, On balanced graphs. Math. Program. 105, 233–250 (2006)MathSciNetMATH
8.
F. Bonomo, M. Chudnovsky, G. Durán, Partial characterizations of clique-perfect graphs I: subclasses of claw-free graphs. Discrete Appl. Math. 156, 1058–1082 (2008)MathSciNetMATH
9.
F. Bonomo, M. Chudnovsky, G. Durán, Partial characterizations of clique-perfect graphs II: diamond-free and Helly circular-arc graphs. Discrete Math. 309, 3485–3499 (2009)MathSciNetMATH
10.
F. Bonomo, G. Durán, M.C. M.D. Safe, A.K. Wagler, On minimal forbidden subgraph characterizations of balanced graphs. Electron. Note Discrete Math. 35, 41–46 (2009)
11.
F. Bonomo, G. Durán, F. Soulignac, G. Sueiro, Partial characterizations of coordinated graphs: Line graphs and complements of forests. Math. Method Oper. Res. 69, 251–270 (2009)MATH
12.
E. Boros, K. Elbassioni, V. Gurvich, H.R. Tiwary, The negative cycles polyhedron and hardness of checking some polyhedral properties. Ann. Oper. Res. 188, 63–76 (2011)MathSciNetMATH
13.
M. Cai, X. Deng, W. Zang, An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30, 1993–2007 (2001)MathSciNetMATH
14.
M. Cai, X. Deng, W. Zang, A min–max theorem on feedback vertex sets. Math. Oper. Res. 27, 361–371 (2002)MathSciNetMATH
15.
P. Charbit, A. Sebö, Cyclic orders: Equivalence and duality. Combinatorica 28, 131–143 (2008)MathSciNetMATH
16.
Q. Chen, X. Chen, Packing cycles exactly in polynomial time. J. Combin. Optim. 23, 167–188 (2012)MATH
17.
X. Chen, Z. Chen, W. Zang, A unified approach to box-Mengerian hypergraphs. Math. Oper. Res. 35, 655–668 (2010)MathSciNetMATH
18.
X. Chen, G. Ding, X. Hu, W. Zang, A min–max relation on packing feedback vertex sets. Math. Oper. Res. 31, 777–788 (2006)MathSciNetMATH
19.
X. Chen, G. Ding, W. Zang, The box-TDI system associated with 2-edge connected spanning subgraphs. Discrete Appl. Math. 157, 118–125 (2009)MathSciNetMATH
20.
X. Chen, G. Ding, W. Zang, A characterization of box-Mengerian matroid ports. Math. Oper. Res. 33, 497–512 (2008)MathSciNetMATH
21.
X. Chen, X. Hu, W. Zang, A min–max theorem on tournaments. SIAM J. Comput. 37, 923–937 (2007)MathSciNetMATH
22.
M. Chudnovsky, G. Cornuéjols, X. Liu, P.D. Seymour, K. Vušković, Recognizing Berge graphs. Combinatorica 25, 143–186 (2005)MathSciNetMATH
23.
M. Chudnovsky, N. Robertson, P.D. Seymour, R. Thomas, The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)MathSciNetMATH
24.
V. Chvátal, On certain polytopes associated with graphs. J. Combin. Theor Ser. B 18, 138–154 (1975)MATH
25.
W. Cook, On box totally dual integral polyhedra. Math. Program. 34, 48–61 (1986)MATH
26.
W. Cook, L. Lovász, A. Schrijver, A polynomial-time test for total dual integrality in fixed dimension. Math. Program. Study 22, 64–69 (1984)MATH
27.
M. Conforti, G. Cornuéjols, K. Vušković, Balanced matrices. Discrete Math. 306, 2411–2437 (2006)MathSciNetMATH
28.
G. Cornuéjols, Combinatorial Optimization: Packing and Covering (SIAM, Philadelphia, 2001)
29.
G. Cornuéjols, J. Fonlupt, D. Naddef, The traveling salesman problem on a graph and somed related integer polyhedra. Math. Program. 33, 1–27 (1985)MATH
30.
G. Cornuéjols, B. Guenin, F. Margot, The packing property. Math. Program. 89, 113–126 (2000)MathSciNetMATH
31.
G. Cornuéjols, D. Hartvigsen, An extension of matching theory. J. Combin. Theor Ser. B 40, 285–296 (1986)MATH
32.
G. Cornuéjols, W. Pulleyblank, A matching problem with side conditions. Discrete Math. 29, 135–159 (1980)MathSciNetMATH
33.
R. Diestel, Graph Theory, 3rd edn. (Springer, New York, 2005)MATH
34.
35.
G. Ding, L. Feng, W. Zang, The complexity of recognizing linear systems with certain integrality properties. Math. Program. Ser. A 114, 321–334 (2008)MathSciNetMATH
36.
37.
38.
J. Edmonds, Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications (Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, 1969) ed. by R. Guy, H. Hanani, N. Sauer, J. Schöonheim (Gordon and Breach, New York, 1970), pp. 69–87
39.
J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithmis (Algorithmic Press, New York, 1973), pp. 91–96
40.
41.
J. Edmonds, R. Giles, A min–max relation for submodular functions on graphs, in Annals of Discrete Mathematics, vol.  1 (North-Holland, Amsterdam, 1977), pp. 185–204
42.
J. Edmonds, R. Giles, Total dual integrality of linear inequality systems, in Progress in Combinatorial Optimization, ed. by W.R. Pulleyblank (Academic, Toronto, 1984), pp. 117–129
43.
P. Erdös, L. Pósa, On the independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)MATH
44.
U. Faigle, W. Kern, Submodular linear programs on forests. Math. Program. 72, 195–206 (1996)MathSciNetMATH
45.
U. Faigle, W. Kern, On the core of ordered submodular cost games. Math. Program. Ser. A 87, 483–499 (2000)MathSciNetMATH
46.
T. Feder, A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci. 45, 233–284 (1992)MathSciNetMATH
47.
P. Feofiloff, D.H. Younger, Directed cut transversal packing for source-sink connected graphs. Combinatroica 7, 255–263 (1987)MathSciNetMATH
48.
S. Fiorini, N. Hardy, Nadia, B. Reed, A. Vetta, Approximate min–max relations for odd cycles in planar graphs. Math. Program. 110, 71–91 (2007)MathSciNetMATH
49.
J. Fonlupt, D. Naddef, The traveling salesman problem in graphs with some excluded minors. Math. Program. 53, 147–172 (1992)MathSciNetMATH
50.
A. Frank, A coloring question on digraphs, in DMANET, 1998
51.
52.
A. Frank, T. Király, A Survey on covering supermodular functions, in Research Trends in Combinatorial Optimization (Boon, 2008) ed. by W. Cook, L. Lovász, J. Vygen, (Springer, Berlin, 2009), pp. 87–126
53.
A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs. Discrete Appl. Math. 131, 385–400 (2003)MathSciNetMATH
54.
A. Frank, É. Tardos, An application of submodular flows. Lin. Algebra Appl. 114–115, 329–348 (1989)MathSciNet
55.
S. Fujishige, Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics, vol. 58 (Elsevier, London, 2005)MATH
56.
D.R. Fulkerson, Networks, frames, and blocking systems, in Mathematics of the Decision Sciences, Part I, ed. by G.B. Dantzig, A.F. Veinott (American Mathematical Society, Providence, Rhode Island, 1968), pp. 303–334
57.
D.R. Fulkerson, Blocking and antiblocking pairs of polyhedra. Math. Program. 1, 168–194 (1971)MathSciNetMATH
58.
D.R. Fulkerson, Packing rooted directed cuts in a weighted directed graph. Math. Program. 6, 1–13 (1974)MathSciNetMATH
59.
D. Gale, L. Shapley, College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962)MathSciNetMATH
60.
M.R. Garey, D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, New York, 1979)MATH
61.
J. Geelen, B. Guenin, B, Packing odd circuits in Eulerian graphs. J. Combin. Theor Ser. B 86, 280–295 (2002)MathSciNetMATH
62.
A.M.H. Gerards, M. Laurent, A characterization of box \(\frac{1} {d}\)-integral binary clutters. J. Combin. Theor Ser. B 65, 186–207 (1995)MathSciNetMATH
63.
M.X. Goemans, D.P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, in Approximation Algorithms for NP-Hard Problems, ed. by D.S. Hochbaum (PWS Publishing Company, Boston, MA), pp. 144–191
64.
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)MathSciNetMATH
65.
M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988)MATH
66.
M. Grötschel, C. Monma, M. Stoer, Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J. Optim. 2, 474–504 (1992)MathSciNetMATH
67.
M. Grötschel, C. Monma, M. Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res. 40, 309–330 (1992)MathSciNetMATH
68.
B. Guenin, A short proof of Seymour’s characterization of the matroids with the max-flow min-cut property. J. Combin. Theor Ser. B 86, 273–279 (2002)MathSciNetMATH
69.
70.
R.P. Gupta, An edge-coloration theorem for bipartite graphs with applications. Discrete Math. 23, 229–233 (1978)MathSciNetMATH
71.
H. Hirai, Tight spans of distances and the dual fractionality of undirected multiflow problems. J. Combin. Theor Ser. B 99, 843–868 (2009)MathSciNetMATH
72.
T.C. Hu, Multi-commodity network flows. Oper. Res. 11, 344–360 (1963)MATH
73.
K. Ken-ichi, Half integral packing, Erdös-Posá-property and graph minors, in Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1187–1196
74.
K. Ken-ichi, R. Bruce, A nearly linear time algorithm for the half integral disjoint paths packing, in Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 446–454
75.
S. Khanna, J. Naor, F.B. Shepherd, Directed network design with orientation constraints. SIAM J. Discrete Math. 19, 245–257 (2005)MathSciNetMATH
76.
T. Király, J. Pap, Total dual integrality of Rothblum’s description of the stable-marriage polyhedron. Math. Oper. Res. 33, 283–290 (2008)MathSciNetMATH
77.
D. Král, H. Voss, Edge-disjoint odd cycles in planar graphs. J. Combin. Theor Ser. B 90, 107–120 (2004)MATH
78.
M. Laurent, S. Poljak, One-third-integrality in the max-cut problem. Math. Program. 71, 29–50 (1995)MathSciNetMATH
79.
O. Lee, Y. Wakabayashi, Note on a min–max conjecture of Woodall. J. Graph Theorem 38, 36–41 (2001)MathSciNetMATH
80.
81.
L. Lovász, Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267 (1972)MathSciNetMATH
82.
C.L. Lucchesi, D.H. Younger, A minimax relation for directed graphs. J. Lond. Math. Soc. 17, 369–374 (1978)MathSciNetMATH
83.
A.R. Mahjoub, Two-edge connected spanning subgraphs and polyhedra. Math. Program. 64, 199–208 (1994)MathSciNetMATH
84.
85.
C.L. Monma, B.S. Munson, W.R. Pulleyblank, Minimum weight 2-connected spanning networks. Math. Program. 46, 153–172 (1990)MathSciNetMATH
86.
J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944)MATH
87.
E. O’Shea, A. Sebö, Alternatives for testing total dual integrality. Math. Program. 132, 57–78 (2012)MathSciNetMATH
88.
J. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992)MATH
89.
90.
91.
A.D. Pia, G. Zambelli, Half-integral vertex covers on bipartite bidirected braphs: total dual integrality and cut-rank. SIAM J. Discrete Math. 23, 1281–1296 (2009)MathSciNetMATH
92.
W.R. Pulleyblank, Polyhedral combinatorics, in Mathematical Programming – The State of the Art (Bonn, 1982), ed. by A. Bachem, M. Grötschel, B. Korte (Springer, Berlin, 1983), pp. 312–345
93.
W. Pulleyblank, J. Edmonds, Facets of 1-matching polyhedra, in Hypergraph Seminar (Proceedings Working Seminar on Hypergraphs, Columbus, Ohio, 1972), ed. by C. Berge, D. Ray-Chaudhuri (Springer, Berlin, 1974), pp. 214–242
94.
R. Rado, Bemerkungen zur Kombinatorik im AnschluSS an Untersuchungen von Herrn D. König. Sitzungsberichte der Berliner Mathematischen Gesellschaft 32, 60–75 (1933)
95.
U. Rothblum, Characterization of stable matchings as extreme points of a polytope. Math. Program. 54, 57–67 (1992)MathSciNetMATH
96.
T.J. Schaefer, The complexity of satisfiability problems, in Proceedings of 10th ACM Symposimum on Theory of Computing, New York, 1986, pp. 216–226
97.
A. Schrijver, A counterexample to a conjecture of Edmonds and Giles. Discrete Math. 32, 213–214 (1980)MathSciNetMATH
98.
A. Schrijver, Min-max relations for directed graphs. Ann. Discrete Math. 16, 127–146 (1982)MathSciNet
99.
A. Schrijver, Min-max results in combinatorial optimization, in Mathematical Programming: The State of the Art Bonn 1982, ed. by A. Bachem, M. Grötschel, B. Korte (Springer, New York, 1983), pp. 439–500
100.
A. Schrijver, Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions, in Progress in Combinatorial Optimization (Academic Press, Toronto, 1984), pp. 315–361
101.
A. Schrijver, Theory of Linear and Integer Programming (Wiley, New York, 1986)MATH
102.
A. Schrijver, Polyhedral combinatorics, in Handbook of Combinatorics, vol. 2, ed. by R.L. Graham, M. Grötschel, L. Lovász (Elsevier, Amsterdam, 1995), pp. 1649–1704
103.
A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency (Springer, Berlin, 2003)MATH
104.
A. Schrijver, P.D. Seymour, A proof of total dual integrality of matching polyhedra, in Mathematical Centre Report ZN 79/77 (Mathematical Centre, Amsterdam, 1977)
105.
A. Sebö, Minmax relations for cyclically ordered digraphs. J. Combin. Theor Ser. B 97, 518–552 (2007)MATH
106.
P.D. Seymour, The forbidden minors of binary clutters. J. Lond. Math. Soc. 12, 356–360 (1976)MathSciNetMATH
107.
P.D. Seymour, The matroids with the max-flow min-cut property. J. Combin. Theor Ser. B 23, 189–222 (1977)MathSciNetMATH
108.
P.D. Seymour, Decomposition of regular matroids. J. Combin. Theor Ser. B 28, 305–359 (1980)MathSciNetMATH
109.
P.D. Seymour, On odd cuts and plane multicommodity flows. Proc. Lond. Math. Soc. 42, 178–192 (1981)MathSciNetMATH
110.
E. Speckenmeyer, On feedback problems in digraphs, in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 411 (Springer, Berlin, 1989), pp. 218–231
111.
K. Truemper, Matroid Decomposition (Academic Press, Toronto, 1992)MATH
112.
F.T. Tseng, K. Truemper, A decomposition of the matroids with the max-flow min-cut property. Discrete Appl. Math. 15, 329–364 (1986)MathSciNetMATH
113.
D. Vandenbussche, G. Nemhauser, The 2-edge-connected subgraph polyhedron. J. Combin. Optim. 9, 357–379 (2005)MathSciNetMATH
114.
D.R. Woodall, Menger and König systems, in Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642 (1978), pp. 620–635
115.
M. Yuji, Fractional packing in ideal clutters, in Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1181–1186
Metadaten
Titel
Dual Integrality in Combinatorial Optimization
verfasst von
Xujin Chen
Xiaodong Hu
Wenan Zang
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Handbook of Combinatorial Optimization

Print ISBN: 978-1-4419-7996-4

Electronic ISBN: 978-1-4419-7997-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4419-7997-1_57

Premium Partner

    Bildnachweise