caa a22 4500 475769201 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s101079900125 doi (NATIONALLICENCE)springer-10.1007/s101079900125 A probabilistic analysis of a measure of combinatorial complexity for the central curve [Elektronische Daten] [Peter A. Beling, Sushil Verma] Abstract. : We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization. We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve is bounded by n 2-n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces, including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the central curve intersects any sphere centered at the origin at most twice, on average. Springer-Verlag Berlin Heidelberg, 2000 Key words: central curve - linear complementarity - probabilistic analysis nationallicence Beling Peter A. Department of Systems Engineering, University of Virginia, Charlottesville, VA 22903, USA. e-mail: beling@virginia.edu, US aut Verma Sushil i2 Technologies, 303 Twin Dolphin Drive, Suite 210, Redwood City, CA 94065, USA. e-mail: sushil_verma@i2.com, US aut https://doi.org/10.1007/s101079900125 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101079900125 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Beling Peter A. Department of Systems Engineering, University of Virginia, Charlottesville, VA 22903, USA. e-mail: beling@virginia.edu, US aut NATIONALLICENCE 700 1- Verma Sushil i2 Technologies, 303 Twin Dolphin Drive, Suite 210, Redwood City, CA 94065, USA. e-mail: sushil_verma@i2.com, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer