Matchings, matroids and submodular functions

This thesis focuses on three fundamental problems in combinatorial optimization: non-bipartite matching, matroid intersection, and submodular function minimization. We develop simple, efficient, randomized algorithms for the first two problems, and prove new lower bounds for the last two problems. For the matching problem, we give an algorithm for constructing perfect or maximum cardinality matchings in non-bipartite graphs. Our algorithm requires O(n") time in graphs with n vertices, where w < 2.38 is the matrix multiplication exponent. This algorithm achieves the best-known running time for dense graphs, and it resolves an open question of Mucha and Sankowski (2004). For the matroid intersection problem, we give an algorithm for constructing a common base or maximum cardinality independent set for two so-called "linear" matroids. Our algorithm has running time O(nrw-1) for matroids with n elements and rank r. This is the best-known running time of any linear matroid intersection algorithm. We also consider lower bounds on the efficiency of matroid intersection algorithms, a question raised by Welsh (1976). Given two matroids of rank r on n elements, it is known that O(nr1.5) oracle queries suffice to solve matroid intersection. However, no non-trivial lower bounds are known. We make the first progress on this question. We describe a family of instances for which (log2 3)n - o(n) queries are necessary to solve these instances. This gives a constant factor improvement over the trivial lower bound for a certain range of parameters. Finally, we consider submodular functions, a generalization of matroids. We give three different proofs that [omega](n) queries are needed to find a minimizer of a submodular function, and prove that [omega](n2/ log n) queries are needed to find all minimizers.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Harvey, Nicholas James Alexander

Advisor dc:contributor.advisor

• Michel X. Goemans.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/44416

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/44416