Monday, November 24, 2014
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Edmonds' matching polytope is a linear description of the problem of
finding a perfect matching in a graph. Yanakakis asked in 1991 whether
a succinct (polynomial sized) linear description exists that projects
onto Edmonds' matching polytope. Rothvoß recently answered this
question negatively. On the positive side we have known for several
decades that polynomial sized LPs for matching problems exist, as a
consequence of the P-completeness of Linear Programming, and the
existence of polynomial algorithms for matching.
In this talk I will introduce "Weak Extended Formulations" (WEF) for a
polytope Q. Rather than requiring a WEF project onto Q, we insist
that optimizing over the WEF produces the same answers as optimizing
over Q, for those linear objective functions corresponding to problem
instances. I will also introduce a "natural" polytope for the perfect
matching problem (that has Edmonds' polytope as a face), and show how
to construct polynomial sized weak extended formulations for this
polytope. I will finally apply these methods to obtain polynomial
bounds on the non-negative rank of certain slack matrices related to
membership testing of languages.
No background in complexity theory will be assumed.
This is joint work with David Avis, Hans Raj Tiwary, and Osamu
Watanabe.
Colloquium - 16:00
Abstract:
Given a collection of rectangles in the plane, we consider the following two
questions and interplay between them.
The first question is a computational question of computing a maximum
cardinality subset of pairwise non-overlapping rectangles. This problem is
NP-hard, so we focus on approximation algorithms. The problem is equivalent to
approximating the stable set number of a rectangle intersection graph. This
question arises in many areas and has connections to many problems in
theoretical computer science.
The second question is a purely mathematical question of bounding the chromatic
number of a rectangle intersection graph in terms of its clique number. It was
shown in 1960s that any (rectangle intersection) graph having clique number k
can be colored by O(k^2) colors, and there is a lower bound of Omega(k). This
state of the art has not changed for more than 50 years. Narrowing down this
gap is a challenging open problem.
In this talk, I will show a framework that recursively decomposes any rectangle
intersection graph into a collection of degenerate subgraphs (where we know
that both independent set and coloring problems are "easy"). This framework has
been used to obtain the following results.
1. An O(log log n) approximation algorithm for the first problem if the
rectangle representation is given as an input.
2. An improved bound on the second question that holds for a broad class of
rectangles.
(This talk is based on two papers, one of which is joint with Julia Chuzhoy)