### A Bound on Local Minima of Arrangements that Implies the Upper Bound Theorem.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Many numerical computations reported in the literature show only a small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of the corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.

A real matrix A is said to be completely positive (CP) if it can be decomposed as A = BB^T, where the real matrix B has exclusively non-negative entries. Let k be the rank of A and Φ_k the least possible number of columns of the matrix B, the so-called completely positive rank (cp-rank) of A. The present work is devoted to a study of a general upper bound for the cp-rank of an arbitrary completely positive matrix A and its dependence on the ordinary rank k. This general upper bound of the cp-rank...

This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.