×

Cutting planes in combinatorics. (English) Zbl 0581.05015

The author uses two combinatorial problems: packing diamonds into a Chinese checkerboard nd Deza’s proof of a conjecture of Erdős and Lovàsz [M. Deza, J. Comb. Theory, Ser. B, 16, 166-167 (1974; Zbl 0263.05007)] to illustrate how Gomory’s cutting plane method for solving integer linear programming problems can be used to solve combinatorial problems and suggest combinatorial proofs.
Reviewer: D.Bressoud

MSC:

05B30 Other designs, configurations
11H31 Lattice packing and covering (number-theoretic aspects)

Citations:

Zbl 0263.05007
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete math., 4, 305-337, (1973) · Zbl 0253.05131
[2] Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton · Zbl 0108.33103
[3] Deza, M., Une propriété extrémale des plans projectifs finis dans une classe de codes équidistants, Discrete math., 6, 343-352, (1977) · Zbl 0271.94006
[4] Deza, M., Solution d’un problème de Erdös-lovész. J. combin. theory, Ser. B, 16, 166-167, (1974)
[5] Gomory, R.E., Outline of an algorithm for integer solutions to linear programs, Bull. am. math. soc., 64, 275-278, (1958) · Zbl 0085.35807
[6] Gomory, R.E., Solving linear programs in integers, (), 211-216 · Zbl 0096.14505
[7] Gomory, R.E., An algorithm for integer solutions to linear programs, (), 269-302
[8] Penner, S., Elementary problem E 2612. am. math. monthly 83 (1976), 656. solution (by P. vojta), Am. math. monthly, 85, 199-200, (1978)
[9] Schrijver, A., On cutting planes, (), 291-296 · Zbl 0441.90070
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.