File Download
Supplementary

postgraduate thesis: Some polyhedral results in combinatorial optimization

TitleSome polyhedral results in combinatorial optimization
Authors
Issue Date2016
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Xiao, H. [肖汉]. (2016). Some polyhedral results in combinatorial optimization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR.
AbstractMany combinatorial optimization problems can be conceived of as optimizing a linear function over a polyhedron. Investigating properties of the associated polyhedron has been evidenced to be a powerful schema for solving combinatorial optimization problems, especially for characterizing min-max relations. Three different topics in combinatorial optimization are explored in this thesis, which fall within a unified characterization: integrality of polyhedra. Various min-max relations in combinatorial optimization can be formulated into packing and covering problems under the framework of hypergraphs. Packing and covering problems regarding the blocking pair of cycles and feedback sets are studied in this thesis. A min-max relation is established in reducible flow graphs, of which the proof yields a combinatorial algorithm for finding a maximum feedback set packing. The necessary and sufficient condition for integrality of the covering polyhedron of semicomplete digraphs is presented, and min-max relations are conjectured under the same condition. The stable matching problem is of great theoretical interest and practical value in both mathematics and economics. The 2012 Nobel prize in economics being awarded jointly to Roth and Shapley “for the theory of stable allocations and the practice of market design” speaks for its importance. In this thesis, Rothblum’s description of the stable matching polyhedron is generalized to preference systems defined on multigraphs. Moreover, describing stable matchings with a hybrid linear system, i.e., Edmonds-Rothblum system, is discussed. Another investigation concerns kernels, which contain stable matchings as a special case. Originally being a central concept in cooperative games, kernels have turned out to be applicable in various fields such as graph theory, logic and combinatorics. In this thesis, attempts for giving kernels a polyhedral description in two branches of claw-free graphs, namely line graphs and claw-free Berge graphs, are made. Obstructions are detected and polyhedral descriptions are confirmed for kernels in {claw, clique-cutset}-free Berge graphs.
DegreeDoctor of Philosophy
SubjectCombinatorial optimization
Dept/ProgramMathematics
Persistent Identifierhttp://hdl.handle.net/10722/233945

 

DC FieldValueLanguage
dc.contributor.authorXiao, Han-
dc.contributor.author肖汉-
dc.date.accessioned2016-10-07T01:44:37Z-
dc.date.available2016-10-07T01:44:37Z-
dc.date.issued2016-
dc.identifier.citationXiao, H. [肖汉]. (2016). Some polyhedral results in combinatorial optimization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR.-
dc.identifier.urihttp://hdl.handle.net/10722/233945-
dc.description.abstractMany combinatorial optimization problems can be conceived of as optimizing a linear function over a polyhedron. Investigating properties of the associated polyhedron has been evidenced to be a powerful schema for solving combinatorial optimization problems, especially for characterizing min-max relations. Three different topics in combinatorial optimization are explored in this thesis, which fall within a unified characterization: integrality of polyhedra. Various min-max relations in combinatorial optimization can be formulated into packing and covering problems under the framework of hypergraphs. Packing and covering problems regarding the blocking pair of cycles and feedback sets are studied in this thesis. A min-max relation is established in reducible flow graphs, of which the proof yields a combinatorial algorithm for finding a maximum feedback set packing. The necessary and sufficient condition for integrality of the covering polyhedron of semicomplete digraphs is presented, and min-max relations are conjectured under the same condition. The stable matching problem is of great theoretical interest and practical value in both mathematics and economics. The 2012 Nobel prize in economics being awarded jointly to Roth and Shapley “for the theory of stable allocations and the practice of market design” speaks for its importance. In this thesis, Rothblum’s description of the stable matching polyhedron is generalized to preference systems defined on multigraphs. Moreover, describing stable matchings with a hybrid linear system, i.e., Edmonds-Rothblum system, is discussed. Another investigation concerns kernels, which contain stable matchings as a special case. Originally being a central concept in cooperative games, kernels have turned out to be applicable in various fields such as graph theory, logic and combinatorics. In this thesis, attempts for giving kernels a polyhedral description in two branches of claw-free graphs, namely line graphs and claw-free Berge graphs, are made. Obstructions are detected and polyhedral descriptions are confirmed for kernels in {claw, clique-cutset}-free Berge graphs.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshCombinatorial optimization-
dc.titleSome polyhedral results in combinatorial optimization-
dc.typePG_Thesis-
dc.identifier.hkulb5793639-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineMathematics-
dc.description.naturepublished_or_final_version-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats