- FR
- EN
Speaker: Francesco Pisanu (LIPN)
Room: B107
Date: 25/03/2024 14:00
Abstract:
A rational linear system is totally dual integral (TDI) if for every integer linear function, the associated dual problem has an integer optimal solution whenever the optimum is finite. Following the definition, TDI systems with integer right-hand sides characterize integer polyhedra. A TDI system is box-TDI if adding any rational bounds on the variables (i.e. boxes) preserves its TDIness. Classical examples of box-TDI systems are those involved in the Max Flow-Min Cut Theorem of Ford and Fulkerson. In general, box-TDI systems are systems that yield strong min-max relations.
In the early 80s, W.J. Cook proved that any TDI system describing a polyhedron allowing a box-TDI description is also box-TDI. Thus, box-TDIness is a geometrical property, and any polyhedron that can be described by a box-TDI system is called a box-TDI polyhedron.
Recently, a graph characterization of the box-TDIness of the matching polytope has been released. However, this characterization is too restrictive for the perfect matching polytope (PMP). In this talk, we highlight the differences between the two cases and provide insights for tackling the problem of characterizing the box-TDIness of the PMP. We also show that deciding whether the PMP of a graph is box-TDI is equivalent to testing the box-TDIness of its affine hull, which implies that recognizing whether the perfect matching polytope of a given graph is box-TDI can be done in polynomial time.
This is a joint work with Roland Grappe and Mathieu Lacroix
