The Complexity of Recognizing Linear Systems With Certain Integrality Properties

by Li Feng, 馮麗 (Creator)

This dissertation, "The Complexity of Recognizing Linear Systems With Certain Integrality Properties" by Li, Feng, 馮麗, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author.



Abstract of thesis entitled THE COMPLEXITY OF RECOGNIZING LINEAR SYSTEMS WITH CERTAIN INTEGRALITY PROPERTIES submitted by Li Feng for the degree of Master of Philosophy at The University of Hong Kong in September 2007 Many combinatorial optimization problems can be naturally formulated as inte- ger linear programs. Due to the special feature of such a problem, sometimes the corresponding linear programming (LP) relaxation yields an optimal solution that is integral, thus solving the problem; sometimes both the LP relaxation and its dual have integral optimal solutions; sometimes box-integrality property holds for the LP relaxation and its dual. While a basic theme in combinatorial optimization is to identify various problems with these properties, the present thesis is concerned with hardness of recognizing such scenarios. A polyhedron P is called integral if each face of P contains integral vectors. A rational linear system Ax ¸ b; x ¸ 0 is called totally dual integral (TDI) if the maximization problem in the LP-duality equation T T T T minfw xjAx¸b; x¸0g=maxfy bjy A·w ; y¸0g hasanintegraloptimalsolutionyforeveryintegralvectorwforwhichthemaximum is ¯nite. Furthermore, the system Ax¸b, x¸0 is called box-totally dual integral(box-TDI) if the system Ax¸b; x¸0; u¸x¸l is TDI for all rational vectorsu andl,wherecoordinatesofuareallowedtobe+1. Itwasshownthattheproblems of deciding whether a given linear system (1) de¯nes an integral polyhedron, (2) is totally dual integral (TDI), and (3) is box-totally dual integral (box-TDI) are all NP-hard, thereby con¯rming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984.

10.5353/th_b3939198



Linear programming

34 pages, Hardcover

Published January 27, 2017

About the author

Li Feng (Chinese: 李峰; pinyin: Lǐ Fēng), or Feng Li, is a professor of Early Chinese History and Archaeology at Columbia University, where he is director of graduate studies for the Department of East Asian Languages and Culture.