Ideal clutters that do not pack
For a clutter over ground set E, a pair of distinct elements e, f ∈ E are coexclusive if every minimal cover contains at most one of them. An identification of is another clutter obtained after identifying coexclusive elements of . If a clutter is nonpacking, then so is any identification of it. Inspired by this observation, and impelled by the lack of a qualitative characterization for ideal minimally nonpacking (mnp) clutters, we reduce ideal mnp clutters even further by taking their identifications. In doing so, we reveal chains of ideal mnp clutters, demonstrate the centrality of mnp clutters with covering number two, as well as provide a qualitative characterization of irreducible ideal mnp clutters with covering number two. At the core of this characterization lies a class of objects, called marginal cuboids, that naturally give rise to ideal nonpacking clutters with covering number two. We present an explicit class of marginal cuboids, and show that the corresponding clutters have one of Q 6 , Q 2, 1 , Q 10 as a minor, where Q 6 , Q 2, 1 are known ideal mnp clutters, and Q 10 is a new ideal mnp clutter.
| Item Type | Article |
|---|---|
| Copyright holders | © 2017 INFORMS |
| Keywords | Cuboids, Degenerate projective planes, Ideal clutters, Packing property, Replication conjecture, Set-covering polyhedron |
| Departments | Mathematics |
| DOI | 10.1287/moor.2017.0871 |
| Date Deposited | 30 Oct 2019 14:51 |
| Acceptance Date | 2017-05-04 |
| URI | https://researchonline.lse.ac.uk/id/eprint/101837 |
Explore Further
- http://www.scopus.com/inward/record.url?scp=85047071988&partnerID=8YFLogxK (Scopus publication)
- http://www.lse.ac.uk/Mathematics/people/Ahmad-Abdi?from_serp=1 (Author)
- https://pubsonline.informs.org/journal/moor (Official URL)
-
picture_as_pdf -
subject - Accepted Version