×

zbMATH — the first resource for mathematics

Idealness and 2-resistant sets. (English) Zbl 07165807
Summary: A subset of the unit hypercube \(\{0, 1 \}^n\) is cube-ideal if its convex hull is described by hypercube and generalized set covering inequalities. In this note, we study sets \(S \subseteq \{0, 1 \}^n\) such that, for any subset \(X \subseteq \{0, 1 \}^n\) of cardinality at most 2, \(S \cup X\) is cube-ideal.

MSC:
90 Operations research, mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[3] Abdi, A.; Cornuéjols, G.; Pashkovich, K., Ideal clutters that do not pack, Math. Oper. Res., 43, 2, 533-553 (2018)
[4] Balas, E., Facets of the knapsack polytope, Math. Program., 8, 146-164 (1975) · Zbl 0316.90046
[5] Barahona, F.; Grötschel, M., On the cycle polytope of a binary matroid, J. Combin. Theory Ser. B, 40, 1, 40-62 (1986) · Zbl 0596.05018
[6] Chopra, S.; Rao, M. R., The Steiner tree problem I: formulations, compositions and extension of facets, Math. Program., 64, 209-229 (1994) · Zbl 0821.90124
[7] Coppersmith, D.; Lee, J., Indivisibility and divisibility polytopes, (Pardalos, P. M.; Wolkowicz, H., In Novel Approaches to Hard Discrete Optimization. In Novel Approaches to Hard Discrete Optimization, Fields Institute Communications, 37 (2003)), 71-95 · Zbl 1107.90042
[8] Cornuéjols, G., Combinatorial Optimization, Packing and Covering (2001), SIAM: SIAM Philadelphia · Zbl 0972.90059
[9] Cornuéjols, G.; Guenin, B.; Margot, F., The packing property, Math. Program. Ser. A, 89, 1, 113-126 (2000) · Zbl 1033.90099
[10] Edmonds, J.; Johnson, E. L., Euler tours and the Chinese postman problem, Math. Program. Ser. A, 5, 88-124 (1973) · Zbl 0281.90073
[11] Guenin, B., A characterization of weakly bipartite graphs, J. Combin. Theory Ser. B, 83, 112-168 (2001) · Zbl 1030.05103
[12] Hammer, P. L.; Johnson, E. L.; Peled, U. N., Facets of regular 0-1 polytopes, Math. Program., 8, 179-206 (1975) · Zbl 0314.90064
[13] Lee, J., Cropped cubes, J. Combin. Optim., 7, 2, 169-178 (2003) · Zbl 1035.90108
[14] Lucchesi, C. L.; Younger, D. H., A minimax relation for directed graphs, J. Lond. Math. Soc., 17, 2, 369-374 (1978) · Zbl 0392.05029
[15] P. D., Seymour, Graph Theory and Related Topics (1979), Academic Press: Academic Press New York 342-355.
[16] Wolsey, L. A., Faces for linear inequalities in 0-1 variables, Math. Program., 8, 165-178 (1975) · Zbl 0314.90063
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.