Author Description

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 satised 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 sy