4 papers · 1 filter
The rainbow covering number of clean tangled clutters
Ahmad Abdi, Gérard Cornuéjols
In this brief note, we prove a min-min equality for a clean tangled clutter, that the rainbow covering number is equal to the connectivity of its setcore.
Lower bounds for cube-ideal set-systems
Ahmad Abdi, Gérard Cornuéjols, Daniel Dadush +1
A set-system is cube-ideal if its convex hull can be described by capacity and generalized set covering inequalities. In this paper, we use combinatorics, co…
A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs
Gérard Cornuéjols, Siyue Liu, R. Ravi
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted…
Strongly connected orientations and integer lattices
Ahmad Abdi, Gérard Cornuéjols, Siyue Liu +1
Let be a digraph whose underlying undirected graph is -edge-connected, and let be the polytope whose vertices are the incidence vectors of arc sets whose reversal…