For every basis B contained in G  H we need to determine whether there is a better basis B’ contained in G and if so, deliver such a basis B’ . This enables us to find the optimal basis contained in G by successively improving a candidate basis, provided some initial basis is known. Of course, LP-type systems present a more specific realization of this paradigm. First of all, the quality of bases is measured by some function z. In itself, this gives no more than an arbitrary ordering among the bases, but in addition we have required z to extend to all subsets of the ground set H. In particular, unlike the general paradigm above, this requires every basis B to be an optimal basis contained in B.

(i) It should be general enough to cover two concrete problems that we are particularly interested in, namely the polytope distance problem and the minimum spanning ball problem. (ii) It should be specific enough to allow a detailed treatment without drowning in technicalities. The class we get covers problems of minimizing a convex function subject to linear equality and non-negativity constraints.

We start off by introducing the polytope distance problem and derive from this the class of convex programs we are going to consider. We present a solution method for the generic problem in this class, along with time bounds, where we keep track of what concretely happens for the polytope distance problem. Having done this, we apply the developed machinery to obtain a solution for the minimum spanning ball problem. Given two (disjoint and finite) sets P;Q of points in IRd, the objective is to find a pair of points (p; q), p in the convex hull of P, q in the convex hull of Q, such that the length of the difference vector v = p - q is minimized. Formally, if

1 1

:{,.....,}, :{,.....,},



 we let P (resp. Q) denote the (d x r)-matrix (resp. (d x s)-matrix) containing as columns the points of P (resp. Q). PD is the following problem in the variables x = x1; : : : ; xr, y = y1; : : : ; ys.

11 1

, 1, 1,

,0.

 

   

 

This is a quadratic programming problem; this means quadratic objective function and linear constraints whose optimum value is the square of the euclidean distance between conv(P) and conv(Q). Pattern behind PD is the following: minimize a real- valued convex function ,dfIR with its argument p ranging over the nonnegative span of some (d x n) - matrix M , where the coefficients satisfy additional q equality constraints Ax = b. In case of PD, we have p = v, f(v) = vT v, M = (P| - Q) (thus n = r + s) and q = 2 with

1100 0011

1 1







In general, our convex programming problems look as follows. (CP) minimize f() subject to  = Mx, Ax = b, x  0, where p is a d-vector, M a (d x n) - matrix, A a (q x n) - matrix, b a q-vector and x an n-vector. As in LP, inequality constraints Ax < b can be handled by introducing slack variables. We restrict ourselves to equality constraints here. No condition is imposed on M. For PD, this in particular means that we do not require the point sets P and Q to be in any kind of general position. We demand f to be a differentiable function with continuous partial derivatives, which is convex, i.e. for p; p’ and 0 < t < 1, 1'1'ftttftf

Conditions on sub-problems of CP are assumed to hold, and they concern non-degeneracy and uniqueness of solution. For any G  H := [n], consider the problems CP(G) and UCP(G), defined as follows. (CP (G)) minimize f () subject to  = MGxG, AGxG = b, xG  0. (UCP(G)) minimize f () subject to  = MGxG, AGxG = b. The sub-problem CP(G) minimizes f(p) over all feasible x which satisfy the additional restrictions xH-G = 0. In case of PD, this corresponds to a distance computation between sub-polytopes of P and Q specified by G. Where CP(G) asks for the minimum of f over all nonnegative linear combinations with coefficients in some subspace, the relaxation UPD(G) considers any linear combination, and this problem is obtained by simply dropping the non-negativity constraints from CP(G). The `U' stands for `unconstrained', although UCP is not an unconstrained problem in the strict sense. The equality constraints of CP are still present, but later we will see that they are no `real' constraints and that UCP is substantially easier to solve than CP. In case of PD, U C P(G) amounts to a distance computation between the hulls of sub-polytopes.

• B. Gartner and G. M. Ziegler. Randomized simplex algorithms on Klee-Minty cubes.

• In Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science.

• D. Goldfarb and W. Y. Sit. Worst case behavior of the steepest edge Simplex Method. Discrete Applied Mathematics.

 M. Goldwasser. A survey of linear programming in randomized subexponential time. ACM-SIGACT News.

Reading, MA.

• M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg.

• R. G. Jeroslow. The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Mathematics.

• G. Kalai. A subexponential randomized simplex algorithm. In Proceedings of 24th Annual ACM Symposium on Theory of Computing.

 G. Kalai and D. J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of the American Mathematical Society.