Two hard problems in box-Totally Dual Integral polyhedra
Francesco Pisanu  1@  , Mathieu Lacroix  2@  , Roland Grappe  2@  , Roberto Wolfler Calvo  3@  , Patrick Chervet@
1 : Université Paris 13
LIPN, UMR CNRS 7030 - Institut Galilée – Université Paris 13
2 : Laboratoire d'Informatique de Paris-Nord  (LIPN)
Université Paris XIII - Paris Nord, CNRS : UMR7030, Institut Galilée
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -  France
3 : LIPN - Université Paris Nord
université Paris 13

A rational linear system is totally dual integral (TDI) if for every inte-
ger linear function for which the optimum is finite the associated dual
problem has an integer optimal solution. A TDI system is box-TDI
if adding any rational bounds on the variables preserves its TDIness.
Box-TDI systems are systems that yield strong min-max relations such
as the one involved in the Max Flow-Min Cut Theorem of Ford and
Fulkerson. A polyhedron is box-TDI if it can be described by a box-
TDI system.
Box-total dual integral systems and polyhedra received a lot of atten-
tion from the combinatorial optimization community around the 80's.
A renewed interest appeared in the last decade and since then many
deep results appeared involving such systems.
In this talk, we study the complexity of some fundamental questions re-
garding box-TDI polyhedra. First, although box-TDI polyhedra have
strong integrality properties, we prove that Integer Programming over
box-TDI polyhedra is NP-complete, that is, finding an integer point
maximizing a linear function over a box-TDI polyhedron is hard. Sec-
ond, we complement the result of Ding, Tan, and Zang who proved
that deciding whether a given system is box-TDI is co-NP-complete:
we prove that recognizing whether a polyhedron is box-TDI is co-NP-
complete. 


Personnes connectées : 1 Vie privée
Chargement...