Invited Session Wed.2.H 3008

Wednesday, 13:15 - 14:45 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Combinatorics and geometry of linear optimization IV


Chair: Friedrich Eisenbrand



Wednesday, 13:15 - 13:40 h, Room: H 3008, Talk 1

Bernd Gärtner
Abstract optimization problems revisited

Coauthor: Abel Camacho


Abstract Optimization Problems (AOP) generalize linear programs and have been invented with the goal of providing an abstract setting in which the subexponential randomized linear programming algorithms of Kalai and of Matousek, Sharir and Welzl still work. Linear programming abstractions have also been considered recently by Eisenbrand et al., Kim, and others in the context of diameter bounds for polytopes. In this talk, I want to discuss whether and how AOP relate to these new abstractions.



Wednesday, 13:45 - 14:10 h, Room: H 3008, Talk 2

Marco Di Summa
A new bound on the diameter of polyhedra

Coauthors: Nicolas Bonifas, Friedrich Eisenbrand, Nicolai Haehnle, Martin Niemeier


We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rn : Ax ≤ b}, where A ∈ Zm× n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O (Δ2 n4log nΔ ). If P is bounded, then we show that the diameter of P is at most O (Δ2 n3.5log nΔ ).
For the special case in which A is a totally unimodular matrix, the bounds are O (n4log n ) and O (n3.5log n ) respectively. This improves over the previous best bound of O(m16n3(log mn)3) due to Dyer and Frieze.



Wednesday, 14:15 - 14:40 h, Room: H 3008, Talk 3

Edward Kim
Subset partition graphs and an approach to the linear Hirsch conjecture


Combinatorial abstractions of the graphs of polyhedra are receiving renewed interest as an approach to the linear Hirsch and polynomial Hirsch conjectures, since Santos disproved the Hirsch conjecture, which was relevant in the theoretical worst-case running time of the simplex method for linear optimization. We will give a survey of several classical combinatorial abstractions for polyhedral graphs. Then we show how they fit into a more general framework, which leads to some variants of these earlier abstractions. This flexible framework is defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. We present a variant which has superlinear diameter, which together with some combinatorial operations gives a concrete approach for disproving the linear Hirsch conjecture.


  The system of instant Virginia Payday Loans allows any adult U.S. citizen. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.