Aims
In formulating optimization problems as LPs, adding extra variables can greatly reduce the size of the LP. An extension of a polytope is such a formulation that projects onto the original LP formulation of the problem. In this model, LP formulations of some problems in P that have exponential size can be reduced to polynomial size in higher dimensions. Extension complexity is concerned with finding bounds on the sizes of extensions for specific computational problems.This workshop will review the start of the art on the subject and provide ideas for future directions of research.
Date and Venue
Date: June 9 (Mon), 15:00 -- 18:00
Place: Kyoto University Centennial Memorial Hall (A workshop
in Computational Geometry Week 2014)
Program
- [15:00--15:05] Opening: David Avis
(Kyoto and McGill)
- [15:05--15:45] Hans Tiwary
(Charles University)
Extended formulations: Introduction to lower bounding techniques - [15:45--16:25] Kanstantsin Pashkovich (Université
libre de Bruxelles)
Extended formulations: Lower bounds and matching polytope - Short Break (20 min.)
- [16:45--17:25] Yoshio Okamoto
(University of Electro-Communications)
Extended formulations for sparsity matroids - [17:25--17:55] David Avis
(Kyoto and McGill)
Polynomial size matching polytopes
- [17:55--18:00] Closing: Naoki Katoh (Kyoto)
Abstracts of Talks
- Hans Tiwary
(Charles University)
Extended formulations: Introduction to lower bounding techniques
Extended formulations have attracted a lot of attention in recent years with many lower bounds that were a first in the area. In this talk we will discuss some of these lower bounding techniques. The talk is meant to be an introduction to the area and will cover basics of Extended Formulations and a high level view of the techniques themselves. In particular we will discuss techniques used to prove existential lower bounds for arbitrary 0-1 polytopes, lower bounds for polytopes associated with various NP-hard problems. If time permits, we will discuss some open problems.
- Kanstantsin Pashkovich (Université libre de Bruxelles)
Extended formulations: Lower bounds and matching polytope
This talk is dedicated to the new results on the matching polytope and an attempt to differentiate between the matching and the travelling salesman polytope in terms of extended formulations. In the first half, we discuss the recent result of Rothvoss, which shows that the perfect matching polytope does not have an extended formulation of polynomial size. In the second part of the talk, we prove that neither matching polytope nor matroid polytopes can be used as a basis to construct an extended formulation of polynomial size for the travelling salesman polytope.
- Yoshio
Okamoto (University of Electro-Communications)
Extended formulations for sparsity matroids
We show the existence of a polynomial-size extended formulation for the base polytope of a k,l-sparsity matroid. For an undirected graph G=(V,E), the size of the formulation is O(|V||E|) when k ≥ l and O(|V|2|E|) when k ≤ l. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol. Joint work with Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, and Shuji Kijima.
- David Avis
(Kyoto and McGill)
Polynomial size matching polytopes
I will begin by describing a perfect matching polytope that is different from Edmonds' polytope and describe the notion of a weak extended formulation. Then I will show that the new polytope has a weak extended formulation of polynomial size. This implies that perfect matchings in graphs can be solved in polynomial time by optimizing over the weak extended formulation. This is joint work with David Bremner and Osamu Watanabe.
Registration
Free of charge for the registered participants of SoCG 2014.
Others may register from the SoCG
webpage (1-day workshop registration).
Organizers
- David Avis (Kyoto and McGill)
- Naoki Katoh (Kyoto)