A horizon tour of box-total dual integrality
(2026) Computer Science Review — Vol. 61, p. 100928 (2026)
Files
CORE_RP_3352.pdf
Open Access - Adobe PDF
- 990.04 KB
Details
- Authors
- Abstract
- A linear system is totally dual integral (TDI) if, for every linear program with an integer cost vector defined on it, the dual problem admits an integer optimum whenever it is feasible. A linear system is box-totally dual integral (box-TDI) if it remains TDI under the addition of arbitrary rational bounds on its variables. First introduced by Edmonds and Giles in the late 1970s, box-TDIness is a central property in combinatorial optimization, with deep connections to polyhedral integrality, min–max duality, and integer programming. This article provides a self-contained survey of both classical and recent results concerning box-TDI systems and polyhedra. We also discuss complexity aspects and examples from combinatorial optimization where box-TDIness arises naturally. Particular attention is paid to unifying different lines of development in the literature and clarifying the structural properties that underlie the theory. Throughout the paper, we highlight open questions and conjectures, offering a perspective on ongoing and future directions of research.
- Affiliations
Citations
Lancini, E., & Pisanu, F. (2026). A horizon tour of box-total dual integrality. Computer Science Review, 61, 100928. https://doi.org/10.1016/j.cosrev.2026.100928 (Original work published 2026)