When Is the Matching Polytope Box-Totally Dual Integral?

This dissertation, "When is the Matching Polytope Box-totally Dual Integral?" by Lei, Tan, 譚蕾, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: 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: Abstract of thesis entitled WHEN IS THE MATCHING POLYTOPE BOX-TOTALLY DUAL INTEGRAL? submitted by TAN Lei for the degree of Doctor of Philosophy at The University of Hong Kong in August 2015 A rich variety of combinatorial optimization problems can be naturally formu- lated as integer linear programs. One approach to these problems is to consider the corresponding linear programming (LP) relaxations and explore integrality proper- ties satisfied by their constraints. Due to the special structure of the constraint matrix, sometimes the LP-relaxation has an optimal solution that is integral. Thus theoriginalproblemreducestoanLPproblem, therebyadmittingapolynomial-time solution. Sometimes, boththeLP-relaxation anditsdualhaveintegraloptimalsolu- tions. Hence both the original problem and its dual are solvable in polynomial time. Consequently, abeautifulmin-maxtheoremalsofollows. Sometimes, box-integrality property holds for the LP relaxation and its dual. Under what conditions do such integrality properties hold? This question is of both great theoretical interest and practical value; it is also a major concern of operations research and theoretical computer science. The present thesis is devoted to the study of box-total dual integrality enjoyed bythematching polytope. LetG =(V, E) beagraph. Thematching polytopeofG, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds in 1965, P(G) is determined by the following linear system π(G): - x(e)>=0 for each e∈E; - x(δ(v))- x(E[U])Thusthematchingpolytopeformsthefirstclassofpolyhedrawhosecharacterization does not simply follow just from total unimodularity, and its description was a significant breakthrough in polyhedral combinatorics. In 1978, Cunningham and Marsh strengthened Edmonds' matching polytope theorem by showing that π(G) is always totally dual integral. In 1984, Edmonds and Giles initiated the study of graphs G for which π(G) is box-totally dual integral. The main purpose of this thesis is to present a structural characterization of all such graphs.One crux of the characterization is the lack of a proper tool for establishing box-total dual integrality. In the literature, there are only two methods presently available: one involves a condition that can hardly be verified in practice, and the other is based on demanding total unimodularity. Furthermore, neither of them is applicable to the matching polytope under consideration. In this thesis a general and powerful method for establishing box-total dual integrality will be developed, which has a transparent combinatorial nature and can certainly be used to tackle many other important optimization problems. Subjects: Integer programming Combinatorial optimization