Combinatorial Optimization in Matching and Matroid Problems

Abstract

The focus of this proposal is the graph matching and the matroid problems, two fundamental topics in theoretical computer science. Besides its numerous applications, the importance of matching can be testified by the crucial role it has played in the development of algorithm design, graph theory, and polyhedral combinatorics in the last century.

Matroids are an important tool in combinatorial optimization. The matroid intersection problem is a generalization of various

optimization problems and has applications in electric circuit theory, rigidity theory, and network coding.

Although matching and matroid problems have been extensively studied in the past decades, we believe that they are worth a

deeper investigation for two reasons.

(1) New applications pose new challenges and the known techniques are not always adequate.

(2) Some fundamental questions in matching and matroids still remain unanswered. What causes the barrier in improving the running time of the algorithms?

In this project, we choose problems that are of fundamental nature, i.e., in attacking them, we advance the frontier of our knowledge, and/or are of genuine practical interest.

Our goal in this project can be stated as follows:

–Designing fast(er) exact and approximation algorithms for solving matching and matroid problems. In particular, we focus on matching problems under preferences and the maximum weight matroid intersection problem.