×

Characterizing and recognizing generalized polymatroids. (English) Zbl 1327.52018

A generalized polymatroid is a polyhedron given by supermodular and submodular functions p and b, both mapping the empty set to zero and satisfying a “cross-inequality”. Generalized polymatroids generalize polymatroid, contra-polymatroids, base-polyhedra, and submodular polyhedra.
This paper focuses on characterizations and recognition complexity of generalized polymatroids. The main results are the following:
A polyhedron is a generalized polymatroid if it can be defined by set functions p,b such that for every primal objective with finite value some optimal solution is “laminar”, where the latter is a combinatorial property of the support of the solution.
While it is shown that verifying the above characterization is NP-hard, the authors give a polynomial-time algorithm that given a system of linear inequalities checks if a polyhedron is a generalized polymatroid.
Another result is that the known property of integral generalized polymatroids that their intersection is integral in fact characterizes them in the following sense: If the intersection of a polyhedron P with every integral generalized polymatroid is integral, then P is a generalized polymatroid.
Finally, bounded generalized polymatroids are characterized as satisfying certain Minkowski sum equations related to generalized permutahedra.

MSC:

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
90C05 Linear programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ardila, F., Benedetti, C., Doker, J.: Matroid polytopes and their volumes. Discret. Comput. Geom. 43, 841-854 (2010). Corrected version: arXiv:0810.3947 · Zbl 1204.52016
[2] Ardila, F., Doker, J.: Lifted generalized permutahedra and composition polynomials. ArXiv e-prints (2012) · Zbl 1280.52009
[3] Bernáth, A., Király, T.: Covering skew-supermodular functions by hypergraphs of minimum total size. Oper. Res. Lett. 37(5), 345-350 (2009). doi:10.1016/j.orl.2009.04.002 · Zbl 1210.05087 · doi:10.1016/j.orl.2009.04.002
[4] Danilov, V.I., Koshevoy, G.A.: Discrete convexity and unimodularity—i. Adv. Math. 189(2), 301-324 (2004) · Zbl 1066.52016 · doi:10.1016/j.aim.2003.11.010
[5] Ding, G., Feng, L., Zang, W.: The complexity of recognizing linear systems with certain integrality properties. Math. Program. 114, 321-334 (2008) · Zbl 1160.90633 · doi:10.1007/s10107-007-0103-y
[6] Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanam, H., Sauer, N., Schonheim J. (eds.) Combinatorial structures and their applications (Proc. 1969 Calgary Conference), pp. 69-87. Gordon and Breach, New York (1970). Reprinted in M. Jünger et al. (eds.): Combinatorial Optimization (Edmonds Festschrift), LNCS 2570, pp. 1126, Springer, 2003 · Zbl 0665.90073
[7] Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127-136 (1971). (Princeton Symposium Math. Prog. 1967) · Zbl 0253.90027
[8] Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. In: Studies in Integer Programming (1975 Bonn, Germany), Annals of Discrete Mathematics, vol. 1, pp. 185-204. North-Holland (1977) · Zbl 0373.05040
[9] Frank, A.: Generalized polymatroids. In: Hajnal, A., Lovász, L., Sós, V.T. (eds.) Finite and Infinite Sets (Proc. 6th Hungarian Combinatorial Colloquium, 1981), Colloq. Math. Soc. János Bolyai, vol. 37, pp. 285-294. North-Holland (1984) · Zbl 1066.52016
[10] Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discret. Math. 5(1), 25-53 (1992). Preliminary version appeared in Proc. 31st FOCS, pages 708-718, 1990 · Zbl 0782.05054
[11] Frank, A.: Connections in Combinatorial Optimization. No. 38 in Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2011)
[12] Frank, A., Király, T.: A survey on covering supermodular functions. In: Cook, W.J., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization (Bonn 2008), chap. 6, pp. 87-126. Springer, Berlin (2009) · Zbl 1359.05088
[13] Frank, A., Tardos, É.: Generalized polymatroids and submodular flows. Math. Program. 42, 489-563 (1988) · Zbl 0665.90073 · doi:10.1007/BF01589418
[14] Fujishige, S.: A note on Frank’s generalized polymatroids. Discret. Appl. Math. 7(1), 105-109 (1984). doi:10.1016/0166-218X(84)90117-3 · Zbl 0534.05023 · doi:10.1016/0166-218X(84)90117-3
[15] Fujishige, S.: Submodular Functions and Optimization. No. 58 in Annals of Discrete Mathematics. Elsevier (2005)
[16] Hoffman, A.; Schwartz, D.; Hajnal, A. (ed.); Sós, V. (ed.), On lattice polyhedra, No. 18, 593-598 (1976), Amsterdam · Zbl 0361.53056
[17] Murota, K.: Convexity and Steinitz’s exchange property. In: Proceedings 5th IPCO, pp. 260-274. Springer, London (1996) · Zbl 0867.90092
[18] Pap, J.: Recognizing conic TDI systems is hard. Math. Program. 128, 43-48 (2011) · Zbl 1218.90226 · doi:10.1007/s10107-009-0294-5
[19] Papadimitriou, C., Yannakakis, M.: On recognizing integer polyhedra. Combinatorica 10, 107-109 (1990) · Zbl 0718.68044 · doi:10.1007/BF02122701
[20] Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Notices 2009(6), 1026-1106 (2009). doi:10.1093/imrn/rnn153. ArXiv:math.CO/0507163 · Zbl 1162.52007
[21] Postnikov, A., Reiner, V., Williams, L.: Faces of generalized permutohedra. Documenta Math. 13, 207-273 (2008). ArXiv:math.CO/0609184 · Zbl 1167.05005
[22] Schrijver, A.: Proving total dual integrality with cross-free families—a general framework. Math. Program. 29, 15-27 (1984) · Zbl 0531.90076 · doi:10.1007/BF02591726
[23] Schrijver, A.: Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions. In: Pulleyblank, W. (ed.) Progress in Combinatorial Optimization (Silver Jubilee, Waterloo, ON, 1982), pp. 315-361. Academic Press, London (1984)
[24] Schrijver, A.: Supermodular Colourings. In: Lovász, L., Recski, A. (eds.) Matroid Theory, pp. 327-343. North-Holland, Amsterdam (1985) · Zbl 0602.05018
[25] Schrijver, A.: Combinatorial Optimization. Springer, New York (2003) · Zbl 1041.90001
[26] Sebő, A.: Personal, communication, December 2010 · Zbl 0531.90076
[27] Seshadhri, C., Vondrak, J.: Is submodularity testable? ArXiv e-prints (2010) · Zbl 1307.68097
[28] Tardos, É.: Generalized matroids and supermodular colourings. In: Lovász, L., Recski, A. (eds.) Matroid Theory, pp. 359-382. North-Holland, Amsterdam (1985) · Zbl 0602.05020
[29] Tomizawa, N.: Theory of hyperspace (XVI)—on the structures of hedrons (in Japanese). Tech. Rep. CAS82-172, Papers of the Technical Group on Circuits and Systems, Institute of Electronics and Communications Engineers of Japan (1983)
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.