Abstract. With every family of finitely many subsets of a finite-dimensional vector space over the Galois-field with two elements we associate a cyclic transversal polytope. It turns out that those polytopes generalize several well-known polytopes that are relevant in combinatorial optimization, among them cut polytopes as well as stable set and matching polytopes. We introduce the class of lifted odd-set inequalities and prove results demonstrating their strength. In particular, we show that they suffice to describe cyclic transversal polytopes if the union of the sets in the family has rank at most two. We also describe extended formulations for cyclic transversal polytopes and introduce a special relaxation hierarchy for them.

Abstract. We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch conjecture and prove that if there is a pivot rule for the simplex algorithm for which one can bound the number of steps by a polynomial in the diameter plus the number of facets of the polyhedron of feasible solutions, then the general linear programming problem can be solved in strongly polynomial time.

In 1991, Yannakakis [J. Comput. System Sci., 43 (1991), pp. 441--466] proved that no symmetric extended formulation for the matching polytope of the complete graph $K_n$ with $n$ nodes has a number of variables and constraints that is bounded subexponentially in $n$. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of $K_n$. It was also conjectured by Yannakakis that “asymmetry does not help much,” but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in $K_n$ with $\lfloor\log n\rfloor$ edges there are nonsymmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulations of polynomial size exist. We furthermore prove similar statements for the polytopes associated with cycles of length $\lfloor\log n\rfloor$. Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. Compared to the extended abstract [Integer Pgrogramming and Combinatiorial Optimization, Lecture Notes in Comput. Sci. 6080, Springer, New York, 2010, pp. 135--148], this paper not only contains proofs that had been omitted there but also presents slightly generalized and sharpened lower bounds.

We prove that the RANDOM‐EDGE simplex‐algorithm requires an expected number of at most $13n/\sqrt{d}$ pivot steps on any simple d‐polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d‐cubes the trivial upper bound of $2^d$ on the performance of RANDOM‐EDGE can asymptotically be improved by the factor $1/d^{(1-\varepsilon)\log d}$ for every $\varepsilon>0$.

We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the "random edge" rule yields the best asymptotic behavior as well as the most complicated analysis. All other rules turn out to be much easier to study, but also produce worse results: Most of them show essentially worst-possible behavior; this includes both Kalai's "random-facet" rule, which without dimension restriction is known to be subexponential, and Zadeh's deterministic history-dependent rule, for which no nonpolynomial instances in general dimensions have been found so far.