Further talks

Modal title

Modal content

Spring Semester 2010

Date / Time

Speaker

Title

Location

24 June 2010
15:15-16:15

Prof. Dr. Francisco Santos
University of Cantabria, Spain

Details

IFOR talks

Title	A counter-example to the Hirsch conjecture
Speaker, Affiliation	Prof. Dr. Francisco Santos, University of Cantabria, Spain
Date, Time	24 June 2010, 15:15-16:15
Location	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).

A counter-example to the Hirsch conjectureread_more

HG G 19.1

8 July 2010
11:15-12:15

Prof. Dr. François Margot
Tepper School of Business, Carnegie Mellon University, USA

Details

IFOR talks

Title	Intersection Cuts with Infinite Split Rank
Speaker, Affiliation	Prof. Dr. François Margot, Tepper School of Business, Carnegie Mellon University, USA
Date, Time	8 July 2010, 11:15-12:15
Location	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.

Intersection Cuts with Infinite Split Rankread_more

HG G 19.1

15 July 2010
11:15-12:15

Prof. Dr. Jochen Könemann
University of Waterloo, Canada

Details

IFOR talks

Title	Linear Programming Relaxations for Steiner Trees
Speaker, Affiliation	Prof. Dr. Jochen Könemann, University of Waterloo, Canada
Date, Time	15 July 2010, 11:15-12:15
Location	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.

Linear Programming Relaxations for Steiner Treesread_more

HG G 19.1

31 August 2010
14:00-15:00

Dr. Rico Zenklusen
MIT

Details

IFOR talks

Title	Approximation Schemes for Multi-Budgeted Independence Systems
Speaker, Affiliation	Dr. Rico Zenklusen, MIT
Date, Time	31 August 2010, 14:00-15:00
Location	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.

Approximation Schemes for Multi-Budgeted Independence Systemsread_more

HG G 19.1

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined