## Invited Session Wed.1.H 3008

#### Wednesday, 10:30 - 12:00 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Combinatorics and geometry of linear optimization III

**Chair: Jesus Antonio De Loera and Antoine Deza**

**Wednesday, 10:30 - 10:55 h, Room: H 3008, Talk 1**

**Shinji Mizuno**

An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables

**Coauthor: Tomonari Kitahara**

**Abstract:**

Kitahara and Mizuno obtained an upper bound for the number of different

solutions generated by the primal simplex method with Dantzig's (the most negative) pivoting rule. In this talk, we extend the result to the primal simplex method with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. We see that the upper bound is fairly tight by using a variant of Klee-Minty's LP. The upper bound is applied to a linear programming problem with totally unimodular matrix. We also get a similar bound for the dual simplex method.

**Wednesday, 11:00 - 11:25 h, Room: H 3008, Talk 2**

**Ilan Adler**

The equivalence of linear programs and zero-sum games

**Abstract:**

In 1951, Dantzig showed the equivalence of linear programming problems and two-person zero-sum games. However, in the description of his reduction from linear programs to zero-sum games, he noted that there was one case in which the reduction does not work. This also led to incomplete proofs of the relationship between the Minimax Theorem of game theory and the Strong Duality Theorem of linear programming. In this Talk, I fill these gaps. In particular, I’ll present two complete strongly polynomial reductions of LP’s to zero-sum games, a Karp-type reduction which is applicable to LP’s with rational (as well as algebraic) data, and a Cook type reduction which is applicable to LP’s with real data. The key for both reductions are procedures to solve a system of linear constraints by an oracle capable of determining either feasibility or unboudedness of the system. I’ll also discuss the relationship between the Minimax Theorem and the Strong Duality Theorem.

**Wednesday, 11:30 - 11:55 h, Room: H 3008, Talk 3**

**Uri Zwick**

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

**Coauthors: Oliver Friedmann, Thomas Dueholm Hansen**

**Abstract:**

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially

all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form~*2*^{Ω(n\alpha)}, for some *α>0*) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

The first randomized pivoting rule considered is random-edge, which among all improving pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule considered is random-facet, a more complicated randomized pivoting rule suggested by Kalai and by Matou{\v{s}}ek, Sharir and Welzl. Our lower bound for the random-facet pivoting rule essentially matches the subexponential upper bounds given by Kalai and by Matou{\v{s}}ek et al. Lower bounds for random-edge and random-facet were known before only in abstract settings, and not for concrete linear programs.