Title: Ideal clutters that do not pack
| Speaker: | Ahmad Abdi |
| Affiliation: | University of Waterloo |
| Location: | MC 6486 |
Abstract:
In an attempt to produce an analogue of the Weak Perfect Graph Theorem for set covering problems, Conforti and Cornuejols (1993) made the following conjecture: if a clutter has the packing property, then so does every replication of it. By using the celebrated result of Lehman, this conjecture equivalently predicts that an ideal minimally non-packing (mnp) clutter does not have replicated elements. Cornuejols, Guenin and Margot (2000) conjecture that not only is this true, but every ideal mnp clutter has covering number 2.
We
prove
that
among
ideal
mnp
clutters,
those
with
covering
number
2
indeed
have
a
central
role;
a
qualitative
characterization
theorem
for
these
clutters
is
also
proved.
At
the
core
of
this
characterization
lies
a
class
of
objects,
called
marginal
cuboids,
that
naturally
give
rise
to
ideal
non-packing
clutters
with
covering
number
2.
We
present
an
explicit
class
of
marginal
cuboids,
and
provide
an
excluded
minor
characterization
for
it,
where
one
of
the
excluded
minors
is
a
new
ideal
mnp
clutter
on
10
elements.
Joint
work
with
Gerard
Cornuejols
and
Kanstantsin
Pashkovich.