We show that the complexity to solve linear programming problems, using standard linear algebra, can be reduced to O([n3/lnn]L) operations, where n is the number of variables in a standard form problem with integer data of bit size L. Our technique combines partial updating with a preconditioned...

We consider a new nonlinear relaxation for the Constrained Maximum-Entropy Sampling Prob- lem - the problem of choosing the s x s principal submatrix with maximal determinant from a given n x n positive definite matrix, subject to linear constraints. We implement a branch-and- bound algorithm...

Let C [included] R[exp.n] be a convex set. We assume that [norm.x][infinity]≤1for all x [belong] C; and that C contains a ball of radius 1/R. For x [belong] R[exp.n] , r [belong] R, and B an nxn positive definite matrix, let E (x,B,r) ={y|(y - x) [exp.t] B(y - x) ≤ r[exp.2]}. A [bêta]...

We consider the volumetric cutting plane method for finding a point in a convex set that is characterized by a C [included] Rn separation oracle. We prove polynomiality of the algorithm with each added cut placed directly through the current point, and show that this “central cut” version of...