Tuesday
September 14, 2010 |
Gennadiy Averkov, University of Magdeburg, Germany
Minimal polynomial descriptions of arbitrary polyhedra
Time: 11:00-12:00
Room: HG G 19.2
|
| Abstract: |
This is a joint work with Ludwig Bröcker.
Bosse, Grötschel and Henk asked whether an arbitrary d-dimensional polytope can be described by d polynomial inequalities, i.e., in the form p1>=0,...,pd>=0, where p1,...,pd are d-variate polynomials. This question is answered in positive and the corresponding theorem is also extended to the case of unbounded polyhedra. In this talk I will sketch the proof and present some related problems. If time allows I will also discuss questions on approximation of convex sets by polynomials. |
|
Tuesday
August 31, 2010 |
Rico Zenklusen, MIT
Approximation Schemes for Multi-Budgeted Independence Systems
Time: 14:00-15:00
Room: HG G 19.1
|
| Abstract: |
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Some classical optimization problems, such as maximum spanning tree and forest, shortest path, (perfect) matching, independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. For two or more budgets, typically only randomized multi-criteria approximation schemes are available, which return slightly infeasible solutions. Not much is known however for strict budget constraints: the goal of this talk is to fill this gap for several of the above-mentioned problems.
It is not hard to see that the above-mentioned problems whose solution sets do not correspond to independence systems are inapproximable already for two budget constraints. For the remaining problems, we present approximation schemes for a constant number k of budget constraints using a variety of techniques:
i) we present a simple and widely applicable mechanism to transform multi-criteria approximation schemes into pure approximation schemes. This leads to deterministic and randomized approximation schemes for various of the above-mentioned problems;
ii) we show that points in low-dimensional faces of matroid polytopes are almost integral. Exploiting this fact, we obtain a deterministic approximation scheme for k-budgeted matroid independent set;
iii) we present a deterministic approximation scheme for 2-budgeted matching. The backbone of this result is a purely topological property of curves in R2.
This is joint work with Fabrizio Grandoni. |
|
Thursday
July 15, 2010 |
Jochen Könemann, University of Waterloo, Canada
Linear Programming Relaxations for Steiner Trees
Time: 11:15-12:15
Room: HG G 19.1
|
| Abstract: |
This talk focuses on the classical NP-hard Steiner tree problem, where one is given a weighted undirected graph G and a vertex subset R of so called terminals. The goal is to find the cheapest tree T that spans R, and may contain other, so called Steiner vertices.
Very recently, a number of elegant new Steiner tree approximation algorithms have been proposed that are based on strong linear programming relaxations for the problem. I will survey these LP relaxations, discuss some of their properties, and describe their use in the design of approximation algorithms.
Some of the results presented are based on joint work with David Pritchard, and Deeparnab Chakrabarty. |
|
Thursday
July 8, 2010 |
François Margot, Tepper School of Business, Carnegie Mellon University, USA
Intersection Cuts with Infinite Split Rank
Time: 11:15-12:15
Room: HG G 19.1
|
| Abstract: |
We consider mixed integer linear programs where the integer variables are expressed in terms of the nonnegative continuous variables. In the case of two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a bounded convex set P is finite if and only if the integer points on the boundary of P satisfy a certain "2-hyperplane property". The Dey-Louveaux characterization is a consequence of this more general result.
Joint work with A. Basu and G. Cornuejols.
|
|
Thursday
June 24, 2010 |
Francisco Santos, University of Cantabria, Spain
A counter-example to the Hirsch conjecture
Time: 15:15-16:15
Room: HG G 19.1
|
| Abstract: |
The Hirsch conjecture, stated in 1957, said that if a polyhedron is defined by $n$ linear inequalities in $d$ variables then its combinatorial diameter should be at most $n-d$. That is, it should be possible to travel from any vertex to any other vertex in at most $n-d$ steps (traversing an edge at each step).
The conjecture was posed and is relevant in the context of the simplex method in linear programming. The simplex method, after all, finds the optimal solution by moving from vertex to vertex along the edges of the feasibility polyhedron. Experimentally, the simplex method usually finishes in a linear number of steps, but examples where certain choices of pivot rules lead to exponentially long paths exist, and no pivot rule is known that can be proved to always finish in a polynomial number of steps. Even if other methods for linear programming are proved to be polynomial (Karmakar, Khachiyan), the simplex method remains one of the methods most often used in practice.
From a complexity theory point of view, it is also significant that the known methods are polynomial in the "bit complexity" model, but a polynomial pivot rule for the simplex method would provide a "strongly polynomial" algorithm, that is, one that is polynomial also in the "real machine" model. The question whether such a "strongly polynomial" method exists for linear programming was included by S. Smale in his list of "Mathematical problems for the next century" (AMS, 2000). Of course, a polynomial pivot rule can only exist if the combinatorial diameter is polynomially bounded.
The unbounded case was disproved by Klee and Walkup in 1967. In this talk I will describe the construction of the first counter-example to the bounded case (a polytope). |
|
