# «Discrete and Lexicographic Helly Theorems and their Relations to LP-Type Problems Thesis submitted for the degree of “Doctor of Philosophy” by ...»

Now we show that the Locality Condition is met, that is, for all S ⊆ S, and for all S ⊂ S such that ω(S ) = ω(S ) = −∞ and for each e = (xi, v) ∈ S, if ω(S ∪ {e}) ω(S ) then ω(S ∪ {e}) ω(S ). Let S∗ = S ∪ {e} and S∗ = S ∪ {e}. Let σ, τ be a pair of optimal strategies in G(S ). By Observation 11.3.1, σ, τ is also a pair of optimal strategies in G(S ), so all vertices in the game G(S ) are stable with respect to the pair of optimal strategies σ, τ. If ω(S ∪ {e}) = ω(S∗ ) ω(S ) then σ, τ is not a pair of optimal strategies in G(S∗ ), and there is at least one vertex in V which is unstable in G(S∗ ). Since all the vertices in G(S ) are stable, the only vertex in G(S∗ ) which is unstable is xi (xi is the only vertex in V which has diﬀerent sets of outgoing edges in G(S ) and in G(S∗ )). Thus xi is also unstable in G(S∗ ). Due to Lemma 11.2.6 and ** Lemma 11.2.**

3, as explained at the end of the proof of Observation 11.3.1, we get that ω(S ∪ {e}) ω(S ) as needed. Considering the combinatorial dimension of the problem, we note that a basis B (in the LP-type sense) for any S ⊆ S is the set of d edges corresponding to an optimal strategy σ, for player 1 in the sub-game G(S ) (i.e., B = Sσ ). Hence the corresponding LP-type problem is d-dimensional.

For every D ⊆ D and S ⊆ S we say that G(S, D ) = (V, D ∪ S ∪ AA) is a sub-game of G if G(S, D ) is a sub-game of G with respect to edges outgoing from both min and max vertices. We prove the following Lemma in a similar way we proved Lemma 11.3.2.

** Lemma 11.3.**

3 A Simple Stochastic Game (V = X ∪N ∪A∪{v0, v1 }, S ∪D ∪AA) that halts with probability 1 is an m-dimensional dual LP-type problem (D, ν) where ν is as deﬁned in (11.6) and m = |D|.

where the outdegrees of all the average vertices is 2 and the weights of the edges outgoing from the average vertices are all 2, by using the reduction of Zwick and Paterson (see ﬁrst half of Section 6 in [ZP96]). Each average vertex of outdegree k 2 we replace by a binary tree with k leaves. This increases the number of average vertices and average edges by at most |AA|. We replace each binary average vertex with non-equal probabilities, by a binary tree with O(log l) leaves and probabilities 1 on all its edges, as done in the reduction of Zwick and Paterson (recall that we denote by l the biggest denominator of the (rational) probabilities).

In this way the number of average vertices in the resulted game G is O(|AA| log l) (i.e., O(p2 log l) where p = |A| is the number of average vertices in G), and the number of edges outgoing from these vertices is O(|AA| log l). We note that GT has the same sink, min and max vertices, and the same edges outgoing from the min and max vertices, as in the original game G, so N T = N, X T = X, v0 = v0, v1 = v1, DT = D and T T

** TS = S.**

Suppose ﬁrst that d ≤ m. We solve the SSG GT by the algorithm of [SW92]. By Lemma 11.3.2 the SSG, G(S) = GT = (V T, D ∪ S ∪ AAT ), is a d-dimensional LP-type problem (S, ω), so the algorithm correctly solves the problem. As explained in the end of Subsection 6.2, Function lptype runs in O(nb (tv n + tb )) √ expected time where nb = e d log d is the number of basis computations, tv is the time needed to perform a violation test and tb is the time needed to perform a basis computation.

A basis for any feasible S ⊆ S is a set B = Sσ where σ is an optimal strategy with respect to τ (σ) for the sub-game G(S ). An edge e = (xi, z) violates B (Violation(B, e) =true) if and only if vσ,τ (xi ) = max{vσ,τ (z), vσ,τ (σ(i))}. This can be checked in constant time, so tv = O(1).

Let σ be the strategy obtained from σ by changing the strategy at vertex xi (i.e., ∀i = j, σ (j) = σ(j) and σ (i) = z). A basis computation for B ∪ {e} (Basis(B, e)) is done by deciding which strategy amongst σ, σ is optimal in the game (V T, D ∪ B ∪ {e} ∪ AAT ). In order to decide this we need to ﬁnd an optimal strategy of player 0 with respect to σ, i.e., to ﬁnd an optimal strategy of player 0 in the sub-game G(Sσ ).

This sub-game is equivalent to a game with only min and average vertices, so it is suﬃcient to solve the linear program stated in Lemma 11.2.5 corresponding to it. Since in GT all the probabilities are 1, this is also true for any of its sub-games. Hence the constants in the LP program are 0, 1 and 1, so the algorithm of Khachian [Kh79] solves the LP program in strongly polynomial time and tb = poly(n).

Finally, if d m we use sub-games with respect to edges outgoing from min vertices, and Lemma 11.3.3 instead of Lemma 11.3.2.

**Due to Lemma 11.2.2 we get:**

Corollary 11.4.2 The decision problem corresponding to Simple Stochastic Games is solvable in strongly √ eO( min{d log d,m log m}) × poly(n) expected time.

Since DPG’s, MPG’s and PG’s are all strongly polynomially reducible to SSG’s that halt with probability 1 we get Corollary 11.4.3 Discounted Payoﬀ Games, Mean Payoﬀ Games and Parity Games are all solvable in √ strongly eO( min{d log d,m log m}) × poly(n) expected time.

Theorem 11.5.2 A binary Simple Stochastic Game (V, D ∪ S ∪ AA) that halts with probability 1 is solvable √ in strongly eO( min{d,m}) × poly(n) expected time.

**Again, due to Lemma 11.2.2 we get:**

Corollary 11.5.3 The decision problem corresponding to binary Simple Stochastic Games is solvable in √ strongly eO( min{d,m}) × poly(n) expected time.

11.6 Concluding remarks It is possible (and maybe even more natural) to formulate the SSG decision problem as a discrete LP-type problem. Let Λ = I ∪ {∞, −∞} be as before. Let σ(S, D ), τ (S, D ) be an arbitrary pair of optimal R

Due to this deﬁnition, Lemma 11.3.2 and Lemma 11.3.3, we get that for every S ⊆ S, µ(S, D) = ω(S ) is a d-dimensional LP-type problem and for every D ⊆ D, µ(S, D ) = ν(D ) is an m-dimensional dual LP-type problem. Hence, (S, D, µ) is a (d, m)-dimensional discrete LP-type problem.

Acknowledgment I thank Uri Zwick who brought the paper by Ludwig [Lu95] to my attention.

Chapter 12 The weighted lexicographic rectilinear 1-center problem in the plane In this chapter we present an optimal O(n) time algorithm for the weighted lexicographic rectilinear 1center problem in the plane and prove that calculating the optimal value of the objective function requires Θ(n log n) time under the algebraic computation tree model. We use here several geometric observations and the decimation technique. We note that the term “lexicographic” has a diﬀerent meaning than it has in the rest of this thesis. The material in this chapter previously appeared in [Hal03].

We note that this LP problem can be solved in linear time by algorithms such as the ones of Megiddo [Me83a],[Me84].

It is well known ([FW74]) that by applying a linear transformation on each point in P 1 we get a transformed set of points P ∞ = {p∞,..., p∞ } such that the rectilinear norm l1 in P 1 becomes the l∞ norm in 1 n P ∞, and Problem (12.1) is equivalent to

which we call the weighted planar 1-center with l∞ norm problem. We note that this problem can be formulated as an LP problem using similar arguments as above. We also note that the linear transformation can be done in linear time, so both 1-center problems (12.1) and (12.3) are reducible to each other in linear time. It is also possible to solve the weighted planar 1-center with l∞ norm problem directly by decomposing it into two weighted 1-center problems on the real line ([FW74]).

While the solutions of the weighted 1-center problem on the real line and the weighted planar 1-center problem with l2 norm are unique, the solution of the weighted rectilinear 1-center in the plane, Problem (12.1), is not necessarily unique. In this case we are interested to choose from the set of optimal centers one that satisﬁes some additional properties. It is natural to look at the weighted lexicographic rectilinear 1-center problem in the plane which is deﬁned in [O97]. In this problem we are given the same input as for the non-lexicographic corresponding problem. The goal is to ﬁnd a point p1 ∈ I 2 which minimizes the R scalar c1 as deﬁned in (12.1), as well as the distances vector

where d1 : I 4 →I is the rectilinear distance between two points in the plane and q is the function that R R arranges the components of a multi-set of real elements in non-increasing order. Functions similar to q have already been used in the past (e.g., Kohlberg [Ko72] and Ogryczak [O97]). The location of the center should lexicographically minimize the weighted distances between n customer locations given in P 1, and the service center p1. In this way not only the maximal weighted distance from points in P 1 to p1 is of our concern, but also all of the remaining n − 1 weighted distances.

We deﬁne the weighted lexicographic planar 1-center with l∞ norm problem (lex1-center problem, in short) with the same input as for the non-lexicographic corresponding problem. The goal is to ﬁnd a point p∞ ∈ I 2R which minimizes the distances vector

where d∞ : I 4 →I is the distance with l∞ norm between two points in the plane. We note that, as above, R R both lex1-center problems (12.4) and (12.5) are reducible to each other in linear time. We are unaware of any previous linear time algorithms for these problems.

Example 12.1.1 Let p∞ = (−4, 1); p∞ = (6, −1); p∞ = (3, 2); p∞ = (2, −3) and p∞ = (5, 0) be 5 points in the plane. Let P ∞ = {p∞,..., p∞ } with weights ω1 =... = ω5 = 1 be the input for the lex1-center problem.

The set of optimal centers for the (non-lexicographic) planer 1-center with l∞ norm is the compact vertical interval [(1, −3), (1, 2)]. We note that the x-coordinate of the interval is determined by points p∞ and p∞.

The optimal center of the corresponding lexicographic problem is p∞ = (1, −0.5), the white circle in Figure 1 below. The optimal distances vector is (5, 5, 4, 2 2, 2 1 ).

Observation 12.1.2 Given a set P of n points on the real line, it takes Ω(n log n) time to compute the distances vector, Q(P ), of the lexicographic 1-center on the real line.

Proof: We reduce sorting to the lex1-center on the real line problem. Given a set R = {r1,..., rn } of n real numbers we ﬁnd in linear time rmax, rmin the maximal and minimal numbers in R, respectively. We then construct in linear time an instance of the lex1-center problem with the set

and equal weights to all its points. The optimal center is clearly p = rmax and the distances vector Q(P ) yields the sorting of R.

Conclusion: Given a set P of n points in the plane, it takes Ω(n log n) time to compute the distances vector, Q(P ), of the weighted lexicographic planar 1-center problem in either l1, l∞ or l2 norm.

From now on, throughout this chapter, we will refer only to problems in the l∞ norm, and will therefore omit the ∞ superscript from our notation.

Organization of this chapter: In the following 3 subsections we solve the planar lex1-center problem.

In Subsection 12.2 we consider a restricted version of the lex1-center problem, where the x-coordinate of the center must be a given value. We show that this problem is closely related to a geometric problem which we call the min rays problem. We give a linear time solution algorithm for the min rays problem in Subsection 12.3. In Subsection 12.4 we ”put it all together” and solve the entire lex1-center problem in linear time. In the last subsection we formulate some generalizations of the problem, such as the lex1-center in I d, all of which we solve in linear time.

R 12.2 The restricted lex1-center problem vs. the min rays problem In the restricted lex1-center problem, in addition to the input for the lex1-center problem (12.5), we are also given x@ ∈ I The goal is to ﬁnd a point which minimizes the following function of the single variable y R.

(Intuitively, in the restricted lex1-center problem the x-coordinate of the center is ﬁxed to be x@.) We denote by p@ = (x@, y @ ) ∈ I 2 an optimal solution for Problem (12.6).

R We consider now another formulation for this problem. For every pair of points p = (x, y) and p = (x, y ) we deﬁne dx (p, p ) = |x − x | to be the horizontal distance between p and p. Similarly, we deﬁne dy (p, p ) = |y − y | to be the vertical distance between p and p. Thus d(p, p ) = max{dx (p, p ), dy (p, p )} is the distance between p and p with l∞ norm. For i = 1,..., n, let

Next, we deﬁne a problem, called the min rays problem, and show it is equivalent to the restricted lex1-center problem. In the min rays problem we are given the same input as for the restricted lex1-center problem.

The goal is to ﬁnd

Example 12.2.1 The min rays problem corresponding to the lex1-center problem given in Example 1 is − + shown in Figure 2. The rays r3 and r4, corresponding respectively to points p∞ and p∞ determine the optimal solution c = 2 2 and y = − 2.

Observation 12.2.2 If V = {v1,..., vn } and V = {v1,..., vn } are sets of n real numbers each satisfying that vi ≥ vi for i = 1,..., n then q(V ) ≥L q(V ).

We are now ready to prove Theorem 12.2.3 Let y $, c$ be an optimal solution of the min rays problem. Then (x@, y $ ) is an optimal center in the corresponding restricted lex1-center problem.