On matrices with the Edmonds-Johnson property arising from bidirected graphs. (English) Zbl 1384.05107
Summary: In this paper we study totally half-modular matrices obtained from \(\{0, \pm 1 \}\)-matrices with at most two nonzero entries per column by multiplying by 2 some of the columns. We give an excluded-minor characterization of the matrices in this class having strong Chvàtal rank 1. Our result is a special case of a conjecture by A. M. H. Gerards and A. Schrijver [Combinatorica 6, 365–379 (1986; Zbl 0641.05039)]. It also extends a well known theorem of J. Edmonds and E. L. Johnson [Math. Program. 5, 88–124 (1973; Zbl 0281.90073)].
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
Keywords:
integer programming; combinatorial optimization; strong Chvàtal rank; Edmonds-Johnson property; excluded minors; bidirected graphsReferences:
| [1] | Appa, G., \(k\)-integrality, an extension of total unimodularity, Oper. Res. Lett., 13, 159-163 (1993) · Zbl 0792.90049 |
| [2] | Appa, G.; Kotnyek, B., Rational and integral \(k\)-regular matrices, Discrete Math., 275, 1-15 (2004) · Zbl 1043.15011 |
| [3] | Appa, G.; Kotnyek, B.; Papalamprou, K.; Pitsoulis, L., Optimization with binet matrices, Oper. Res. Lett., 35, 345-352 (2007) · Zbl 1169.90407 |
| [4] | Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131 |
| [5] | Conforti, M.; Gerards, A. M.H.; Zambelli, G., Mixed-integer vertex covers on bipartite graphs, (Proceedings of IPCO 2007. Proceedings of IPCO 2007, Lecture Notes in Comput. Sci., vol. 4513 (2007)), 324-336 · Zbl 1136.90488 |
| [6] | Conforti, M.; Di Summa, M.; Eisenbrand, F.; Wolsey, L. A., Network formulations of mixed-integer programs, Math. Oper. Res., 34, 194-209 (2009) · Zbl 1218.90133 |
| [7] | Cook, W.; Gerards, A. M.H.; Schrijver, A.; Tardos, É., Sensitivity theorems in integer linear programming, Math. Program., 34, 251-264 (1986) · Zbl 0648.90055 |
| [8] | Cornuéjols, G.; Fonlupt, J.; Naddef, D., The traveling salesman problem on a graph and some related integer polyhdra, Math. Program., 33, 1-27 (1985) · Zbl 0562.90095 |
| [9] | Del Pia, A.; Zambelli, G., Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank, SIAM J. Discrete Math., 23, 3, 1281-1296 (2009) · Zbl 1227.05209 |
| [10] | Edmonds, J.; Matching, E. L. Johnson, Euler tours and the Chinese postman, Math. Program., 5, 88-124 (1973) · Zbl 0281.90073 |
| [11] | A.M.H. Gerards, personal communication, 2007.; A.M.H. Gerards, personal communication, 2007. |
| [12] | Gerards, A. M.H.; Schrijver, A., Matrices with the Edmonds-Johnson property, Combinatorica, 6, 365-379 (1986) · Zbl 0641.05039 |
| [13] | Goemans, M. X., Minimum bounded degree spanning trees, (Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006)), 273-282 |
| [14] | Heller, I.; Tompkins, C. B., An extension of a theorem of Danzig’s, (Kuhn, H. W.; Tucker, A. W., Linear Inequalities and Related Systems (1956), Princeton University Press: Princeton University Press Princeton, N.J.), 247-254 · Zbl 0072.37804 |
| [15] | Hurkens, C. A.J.; Lovász, L.; Schrijver, A.; Tardos, É., How to tidy up your set system?, (Combinatorics. Combinatorics, Colloq. Math. Soc. János Bolyai, vol. 52 (1998), North-Holland), 309-314 · Zbl 0744.05007 |
| [16] | Jain, K., A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, 39-60 (2001) · Zbl 1107.68533 |
| [17] | V. Melkonian, É. Tardos, Approximation algorithms for a directed network design problem, in: Proceedings of IPCO 1999, Graz, 1999.; V. Melkonian, É. Tardos, Approximation algorithms for a directed network design problem, in: Proceedings of IPCO 1999, Graz, 1999. · Zbl 0948.90126 |
| [18] | Schrijver, A., On cutting planes, Ann. Discrete Math., 9, 291-296 (1980) · Zbl 0441.90070 |
| [19] | Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley Chichester · Zbl 0665.90063 |
| [20] | Schrijver, A., Combinatorial Optimization. Polyhedra and Efficiency (2003), Springer-Verlag: Springer-Verlag Berlin-Heidelberg · Zbl 1041.90001 |
| [21] | Tutte, W. T., A homotopy theorem for matroids I, II, Trans. Amer. Math. Soc., 88, 144-174 (1958) · Zbl 0081.17301 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
