×

zbMATH — the first resource for mathematics

Lehman’s theorem and the directed Steiner tree problem. (English) Zbl 1336.90107

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2007
[2] W.G. Bridges and H.J. Ryser, Combinatorial designs and related systems, J. Algebra, 13 (1969), pp. 432–446. · Zbl 0185.03206
[3] M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Approximation algorithms for directed Steiner problems, J. Algorithms, 33 (1999), pp. 73–91. · Zbl 0937.68155
[4] S. Chopra and M.R. Rao, The Steiner tree problem I: Formulations, compositions and extension of facets, Math. Program., 64 (1994), pp. 209–229. · Zbl 0821.90124
[5] M. Conforti, G. Cornuéjols, and G. Zambelli, Integer Programming, Springer, Cham, Switzerland, 2014.
[6] G. Cornuéjols, B. Guenin, and F. Margot, The packing property, Math. Program. Ser. A, 89 (2000), pp. 113–126. · Zbl 1033.90099
[7] G. Cornuéjols, B. Guenin, and L. Tunçel, Lehman matrices, J. Combin. Theory Ser. B, 99 (2009), pp. 531–556.
[8] G.A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. Lond. Math. Soc. (1), 27 (1952), pp. 85–92. · Zbl 0046.41001
[9] R.J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl., 10 (1965), pp. 303–318. · Zbl 0128.37002
[10] J. Edmonds, Optimum branchings, J. Res. Nat. Bur. Standards Sect. B, 71B (1967), pp. 233–240.
[11] J. Edmonds and D.R. Fulkerson, Bottleneck extrema, J. Combin. Theory Ser. B, 8 (1970), pp. 299–306.
[12] L.R. Ford and D.R. Fulkerson, Maximal flow through a network, Canad. J. Math., 8 (1956), pp. 399–404. · Zbl 0073.40203
[13] Z. Friggstad, J. Könemann, A.L. Kun-Ko, M. Shadravan, and M. Tulsiani, Linear programming hierarchies suffice for directed Steiner tree, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 8494, 2014, Springer, Cham, Switzerland, pp. 285–296. · Zbl 1418.90223
[14] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program., 1 (1971), pp. 168–194. · Zbl 0254.90054
[15] D.R. Fulkerson, Packing rooted directed cuts in a weighted directed graph, Math. Program., 6 (1974), pp. 1–13. · Zbl 0283.05104
[16] M.X. Goemans, Arborescence polytopes for series-parallel graphs, Discrete Appl. Math., 51 (1994), pp. 277–289. · Zbl 0802.05040
[17] B. Guenin, A characterization of weakly bipartite graphs, J. Combin. Theory Ser. B, 83 (2001), pp. 112–168. · Zbl 1030.05103
[18] E. Halperin and R. Krauthgamer, Polylogarithmic inapproximability, Proceedings of ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 585–594.
[19] J.R. Isbell, A class of simple games, Duke Math. J., 25 (1958), pp. 423–439. · Zbl 0083.14301
[20] J. Lasserre, An explicit exact SDP relaxation for nonlinear 0-1 programs, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 2081, Springer, Cham, Switzerland, 2001, pp. 293–303. · Zbl 1010.90515
[21] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817. · Zbl 1010.90061
[22] A. Lehman, A solution of the Shannon switching game, J. Soc. Ind. Appl. Math., 12 (1964), pp. 687–725. · Zbl 0137.38704
[23] A. Lehman, On the width-length inequality, Math. Program., 17 (1979), pp. 403–417. · Zbl 0418.90040
[24] L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim., 1 (1991), pp. 166–190. · Zbl 0754.90039
[25] A. Prodon, T.M. Liebling, and H. Gröflin, Steiner’s Problem on 2-Trees, Technical report RO 850315, Ecole Polytechnique de Lausanne, Lausanne, Switzerland, 1985.
[26] T. Rothvoß, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arXiv:1111.5473, 2011.
[27] M. Schaffers, Network Flow Design III. Polyhedral Characterization of the Single Source Fixed Costs Problem on Series-Parallel Graphs, CORE Discussion Paper, Université Catholique de Louvain, Louvain, Belgium, 1991.
[28] A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency, Springer, Berlin, 2003. · Zbl 1041.90001
[29] P.D. Seymour, On Lehman’s width-length characterization, in Polyhedral Combinatorics, W. Cook and P.D. Seymour, eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. I, AMS, Providence, RI, 1990, pp. 107–117. · Zbl 0747.05066
[30] P.D. Seymour, The forbidden minors of binary matrices, J. Lond. Math. Soc. (2), 2 (1976), pp. 356–360. · Zbl 0351.05023
[31] F.B. Shepherd, Applying Lehman’s theorems to packing problems, Math. Program., 71 (1995), pp. 353–367. · Zbl 0863.05052
[32] H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), pp. 411–430. · Zbl 0712.90050
[33] L. Zosin and S. Khuller, On directed Steiner trees, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2002, pp. 59–63. · Zbl 1093.68629
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.