David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Paper
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.
Related
Conference paper
Compression for data archiving and backup revisited
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics