A linear programming instance with many crossover events

Abstract

Crossover events for a linear programming problem were introduced by Vavasis and Ye and provide important insight into the behavior of the path of centers. The complexity of a layered-step interior-point algorithm presented by them depends on the number of disjoint crossover events and the coefficient matrix A, but not on b and c. In this short note, we present a linear programming instance with more than n2/8 disjoint crossover events. © 1996 Academic Press, Inc.