×

zbMATH — the first resource for mathematics

Identically self-blocking clutters. (English) Zbl 1436.90113
Lodi, Andrea (ed.) et al., Integer programming and combinatorial optimization. 20th international conference, IPCO 2019, Ann Arbor, MI, USA, May 22–24, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11480, 1-12 (2019).
Summary: A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from \(\{\{a\}\}\) is nonideal. Our proofs borrow tools from gauge duality and quadratic programming. Along the way we provide a new lower bound for the packing number of an arbitrary clutter.
For the entire collection see [Zbl 1418.90011].
MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI