Deterministic algorithm for solving AOPs must in the worst case examine all bases of the input AOP to find the optimal one. This implies that the randomization used in the previous chapter to obtain sub-exponential bounds was indeed crucial. In other words, while the sub-exponential algorithm can only `fool' itself by coming up with `bad' coin flips , any deterministic algorithm can be fooled by an adversary who will supply just the problem the algorithm cannot handle efficiently. Theorem Let H be a finite set, B  2H a set of bases. For any deterministic algorithm A, there exists an ordering <= of the bases and an improvement oracle ф such that A needs at least |B| - 1 oracle queries to solve ,,HB. Proof. We start A on some problem ,,HB with < and ф not yet determined, and we argue that an adversary answering the oracle queries can construct < and ф `online' in such a way that the algorithm is forced to step through all the bases. When supplied with a query pair (G,B), the adversary will output an answer B’ = ф(G,B) according to two simple rules: (i) the answer B’ is consistent with the previous ones, i.e. there exists an AOP on H and B such that the present and all previous queries have been answered correctly with respect to this AOP. (ii) The answer B’ = B (proving that B is optimal among all subsets of G) is given only if there is no other consistent answer. It is clear by induction that the adversary always has a consistent answer, so the algorithm A steps through a sequence of queries with pairs (G,B) and finally stops. Suppose that less than |B| - 1 queries have been performed. Then there are two bases B1 and B2 which have never been the second component of a query pair. We will show that it is consistent with all answers to assume that B1 = B(H), i.e. B1 is an optimal basis. The same holds for B2, so whatever the algorithm outputs, there is an AOP that is not correctly solved, a contradiction to A being an algorithm for solving any AOP. We are left to prove that B1 = B(H) is a consistent choice. Clearly, this can fail only if some answer has revealed the existence of a larger basis with respect to 1. Since there was no query pair (G,B1), the only remaining possibility for this to happen is that some query (G,B) with B1  G has been answered by B, thus establishing B1  B. But in the first query of this type, B1 was still `free' and could have been returned instead of B, a contradiction to rule (ii).

The bases of LP-type systems as well as the z-values can be identified with GF(2), the vector space of all 0=1-vectors of length over the two-element field GF(2). This ,on the one hand , allows to reinterpret algorithms as flipping games over GF(2) and on the other hand makes linear algebra over GF(2) available as a very useful tool for the analysis of these games. H := 1,.....,hh H := 1,....,hh be two disjoint element sets. For any l, hl and h’l are called conjugate elements. We consider LP-type systems ,,AALHHBz

:||{,|1,}llBBHHBhhforalll

i.e. the bases are all the sets containing exactly one of any two conjugate elements. Every basis has elements and can be identified with a 0/1 vector B~ whose l-th component is defined by

:0,

1,



, The mapping BBdefines a bijection between B

and 2GF

.



11 1

00 20







 





with 1lla for all l (equivalently, A is nonsingular). The objective function zA assigns to any basis B the vector :2AzBABGF where 2GF becomes an ordered set W via decreasing lexicographic order, i.e. a vector is larger than another if it has a zero-entry in the first component where they differ. This agrees with the usual decreasing order of the natural numbers when 0=1-vectors are interpreted as binary numbers in the obvious way . The reason for using decreasing instead of the natural increasing order is merely technical and will become clear soon. Since A is nonsingular, all the bases get distinct values and can uniquely be ordered according to these values.

100 110 111





The following table lists the 0/1-vectors corresponding to the bases, ordered by increasing zA-value. Thus, the all-zero vector is the optimal basis in all problems LA. The following lemma prepares the proof that LA indeed defines an LP-type system. Recall that zA extends to all subsets G of H :max|,}AAzGzBBBBG. Lemma for any G  H  H, B  G basis, the following are equivalent. (i) B = B (G), i.e., ()()AAzBzG. (ii) 0AlzB for all l with ,.llhhG Proof. Assume (i) holds and consider l with ,.llhhG. Then the basis ':{,}llBBhh is in G as well, with '',lAlAezBABABezBA where Ae` coincides with the l-th column of A.

and let ` be minimal such that 'llBB. Then ,,llhhGso 0AlzB Moreover, because of A's shape, ` is also minimal with '',AAllllzBABABzB and this shows '.AAzBzBSince B' was any basis, B = B (G) follows. Theorem For any lower-diagonal, nonsingular matrix

2AGF

Proof. zA extends to 2HR is automatically satisfied if no basis contains another which is the case because all bases have the same size . Condition (3.2) demands that {}AAzGjzGimplies {},AAzBjzB

Recall that the primitive operations needed to solve an LP-type system by Algorithm are the improvement query, {}?AAzBjzB and the basis computation, ':{}BBBj Actually, a basis improvement primitive suffices but in this case we do have a basis computation available. The following lemma shows what the operations look like when we interpret them as operations on the 0/1-vector zA(B) = AB~ rather than on B itself. This reinterpretation subsequently leads to an equivalent formulation of algorithm as a flipping game on objective function values. ,,.llhhjBThen {}AAzBjzB if and only if 1lAB and '{}BBBjif and only if ',lAABFAB where

'

1

FEAGF





 is called the flip at l. Proof. Let us distinguish two cases. If B’ = B, then B’ = B(B U {j}) equivalently means zA(B U {j}) = zA(B), resp. (AB~)` = 0. This in turn holds if and only if 0,....,0,,0,.....00,lAeABequivalent ly '.lAABABFAB If B'  B, then B' = B (B  { j }) if and only if (AB')l =  , where B' = B  ,llhh(this is the only other basis in {})Bj. But then we equivalently get 1lAB and 0,....,0,,0,.....,0llllAABABeABAeABAeABFAB To make this convenient interpretation of basis computations as improving linear transformations of objective function values work, decreasing lexicographic order has been chosen (no linear transformation can improve on the value 00 …. 0, therefore this has to be the optimum value).

123000100100 110,000,010



and the step from basis B to B’ with

2100,110()111ABBetakeszBAB

2''00001 00111

AAzBABFAB

In general, when the flip at l is applied to a vector whose l-th entry has value one, it zeroes this entry and flips values at any other position where Ae` equals one. Since A was lower-diagonal, all these positions are to the right of l, so the vector becomes lexicographically smaller. Note that whether a value to the right of l gets flipped does not depend on the value itself but only on its position in the vector. Moreover, if the flip at l is applied to a vector whose l-th entry has value zero, this vector remains unchanged. Algorithm RF-LPtype works on pairs (G,B) with B  G  H  H, B basis. The procedure RF-FlipA equivalently represents B by V (B) := AB~ and G by the set :|,}llSGlGhhG S(G) contains exactly the subscripts that appear in G - B but does not keep the information whether h` or its conjugate hl is in G - B. However, given B (which uniquely corresponds to V (B)), this information is deductible and G can be recovered Invoking Lemma.

• K. L. Clarkson. Linear programming in O(n3d2) Time. Information Processing Letters.

• K. L. Clarkson. A Las Vegas Algorithm for Linear and Integer Programming when the Dimension is Small. In Proceedings of 29th Annual IEEE Symposium Foundations of Computer Science. (1988).

• T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, MA.

• G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

• M. E. Dyer. On a Multidimensional Search Technique and Its Application to the Euclidean One-Center Problem. SIAM J. Comput.

• M. E. Dyer and A. M. Frieze. A Randomized Algorithm for Fixed-Dimensional Linear Programming. Math. Programming.

• H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete Comput. Geom.

Annual IEEE Symposium on Foundations of Computer Science.

• B. Gartner and E. Welzl. Vapnik-Chervonenkis dimension and pseudo-hyperplane arrangements. Discrete Comput. Geom.

 B. Gartner and E. Welzl. Linear programming randomization and abstract frameworks. In Proceedings of 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1046 of Lecture Notes in Computer Science.