Combinatorial Algorithms for Submodular Function Minimization and Related Problems

algorithms;combinatorial optimization;submodular function minimization;Combinatorics and Optimization

Price, Christopher

University of Waterloo

关键词: algorithms;    combinatorial optimization;    submodular function minimization;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9356/1/Christopher_Price.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Submodular functions are common in combinatorics; examples include the cut capacity function of a graph and the rank function of a matroid. The submodular function minimization problem generalizes the classical minimum cut problem and also contains a number of other combinatorial optimization problems as special cases. In this thesis, we study submodular function minimization and two related problems: matroid polyhedron membership and matroid intersection. A significant contribution concerns algorithms for the latter problems due to Cunningham. In particular, we identify and correct errors in the original proofs of the running time bounds for these algorithms.