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

If P p we say that there are free center points. If P p we set for every P i ≤ p, Ci (G) = Di (G) = −∞.

We deﬁne Op (G) = (OD (G), OS (G)) = ({C1 (G),..., CP (G)}, {D0 (G), D1 (G),..., DP (G)}) ∈ 2D × 2S.

Op (G) is an optimal solution for the discrete p-center problem on G in the sense that the radii on Op (G) and on G are the same.

We now deﬁne the auxiliary variables. For i = 2,..., nl + 1, we set C i (G) = −Ci (G) and Di (G) = −Di (G). For i = 1, nl + 2,..., p, we set C i (G) = Ci (G) and Di (G) = Di (G). Finally, if c C1 (G) we let D1 (G) = D1 (G) = max{h | h Cnl +2 (G) − r}, otherwise we let D1 (G) = min{h | h Cnl +1 (G) + r} and D1 (G) = −D1 (G). We call the interval of length r between D0 (G) and D1 (G) the big interval. For every center Ci (G) we say that the half-open half-closed interval of length r − |Ci (G) − Di (G)| starting (but not containing) from Ci (G) to the direction of c is an improving zone in Op (G). We note that each one of D0 (G) and D1 (G) is covered solely by C1 (G). We also note that for each one of the d-elements which lies outside the big interval there is a center diﬀerent from C1 (G) which covers it. We call any algorithm setting the values for the state and auxiliary variables as deﬁned above a distribution algorithm.

Let us consider an instance of the 3-center problem where D = {1, 1.5, 2.5, 5, 8, 8.75, 11.5, 12} and S = {1.5, 2, 7, 7.5, 10.5, 11}. The radius is 2 and it is realized by putting centers at 2,7 and 10.5. The improving zones are the intervals (2, 3]; [6, 7) and [10, 10.5) and nl = nr = 1. The values of the state variables are

**given in Figure 9.1 below:**

c

1 2 5 7 8 10.5 12 Figure 9.1: An instance of the 3-center problem and the corresponding state variables.

From the deﬁnition of Op (G), it follows that ω(Op (G)) = ω(D, S ). From the deﬁnition of Op (G) we get Observation 9.1.1 OD (G) is the minimal set (by inclusion) such that ω(OD (G), S ) = ω(D, S ) and OS (G) is the minimal set (by inclusion) such that ω(D, OS (G)) = ω(D, S ).

Due to the minimality stated in the observation above we call Op (G) the solution of the discrete abstract problem (D, S, ω). In the next subsection we prove that (D, S, ω) is a discrete LP-type problem and that Op (G) is its unique basis.

For the sake of brevity we will omit the “l” sign from l, l, ≥l and ≤l when comparing between values of the lexicographic functions ν and ω.

Observation 9.1.2 ∀h ∈ D, ω(D ∪ {h}, S ) ≥ ω(D, S ) and ∀h ∈ S, ω(D, S ∪ {h}) ≤ ω(D, S ).

The ﬁrst kind of monotonicity follows from the fact that adding a d-element while keeping the same set of s-elements cannot decrease the radius and from the deﬁnition of function ν. The second kind of monotonicity follows from the fact that adding an s-element while keeping the same set of d-elements cannot decrease the radius and from the deﬁnition of function ν.

Observation 9.1.4 Given the solution Op (D, S ) for (D, S, ω) if there exists h ∈ S, which lies strictly between C1 (D, S ) and D0 (D, S ) then there are no free centers.

This is true since if such h exists and there are free centers then making h a center will decrease the radius and consequently the value of ω, in contradiction to the optimality of Op (D, S ).

The following lemma will serve us when we show that the Locality of Demand Condition is satisﬁed.

Proof: If either one of the conditions is satisﬁed Ci (D, S ) covers h, so rp (D, S ) = rp (D ∪ {h}, S ).

Applying a distribution algorithm on (D ∪ {h}, S ) will result ω(D ∪ {h}, S ) = ω(D, S ). If none of the conditions is satisﬁed there are two possibilities.

In both cases due to the monotonicity (Observation 9.1.2) we get ω(D ∪ {h}, S ) ω(D, S ).

The ﬁrst condition stated in the lemma above is about the existence of i such that the distance of h from Ci (D, S ) does not exceed rp (D, S ). The second condition stated in the lemma above is about the relative position of h with respect to Ci (D, S ) and Di (D, S ) for i = 1,..., p. Since Op (D, S ) is the solution of (D, S, ω) we get that rp (D, S ) = rp (Op (D, S )), Ci (D, S ) = Ci (Op (D, S )) and Di (D, S ) = Di (Op (D, S )) for i = 1,..., p, which implies

Proof: If h lies in an improving zone then there is i such that h lies between Ci (D, S ) and the point which lies at distance r − |Ci (D, S ) − Di (D, S )| units from Ci (D, S ) in the direction of c, so from the deﬁnition of Di (D, S ) moving Ci (D, S ) to h will decrease the value of ν. If h lies between C1 (D, S ) and D0 (D, S ), since there are free center points, we can add a center at h and thus decrease the radius. In both cases we get that ω(D, S ) ∪ {h}) ω(D, S ).

Otherwise, due to Observation 9.1.4 no point from S lies between C1 (D, S ) and D0 (D, S ) so the radius cannot decrease (rp (D, S ) = rp (D, S ∪ {h})). Since h does not lie in an improving zone, applying a distribution algorithm on (D, S ∪ {h}) will result ω(D, S ∪ {h}) = ω(D, S ).

** Lemma 9.1.**

8 Let G = (D, S ) ∈ 2D × 2S and let Op (G) be the solution for the discrete abstract problem (D, S, ω) corresponding to the p-center problem on the line (ω is deﬁned in (9.4)), and suppose there are no free center points. If h ∈ S satisﬁes that ∀s ∈ C(G), h s then ω(D, S ∪ {h}) ω(G) if and only if / C1 (G) is the largest in C(G) and h lies in the improving zone of C1 (G) Proof: Let i ≤ p be such that Ci (G) is the greatest center point in C(G). We recall that a distribution algorithm pushes the center points as much as possible towards the center of the big interval so the points in the big interval cannot be covered by any of the p − 1 centers diﬀerent from C1 (G).

If i = 1, the closest center to h is the one of the big interval. Let h∗ = max{h ∈ D | h C1 (G) − rp (G)} be the closest point to the left of the big interval, which C1 (G) does not cover. Let h be the closest point in D to the right of h∗. h is covered by C1 (G). In the optimal solution Op (G), p − 1 centers are needed to cover Dh∗ with radius rp (G), and it is not possible to cover Dh with p − 1 centers with radius rp (G). From Observation 9.1.3 and since h lies to the right of C1 (G), there are at least p − 1 centers in Op (D, S ∪ {h}) which cover Dh∗ with radius at most rp (G) and it is not possible to cover Dh with p − 1 centers with radius at most rp (G). Hence, the rightmost center in Op (D, S ∪ {h}) must cover at least the points in D h. We get that in the solution for the 1-center problem on (D h, S ∪ {h}), the radius is smaller than rp (G) if and only if h lies in the improving zone of C1 (G).

If i = 1, the interval centered at Ci (G) with radius rp (G) covers all the d-elements that the interval with the same radius centered at h covers, so making h a center cannot decrease the value of ω.

Proof: If h lies in an improving zone then there is i such that locating a center at h instead of the center Ci (G) will result a smaller value on ν and consequently on ω.

Suppose by negation that h does not lie in an improving zone of any center and that ω(D, S ∪ {h}) ω(D, S ). We ﬁrst show that rp (D, S ∪ {h}) rp (D, S ). (9.5) If rp (D, S ∪{h}) = rp (D, S ) we apply a distribution algorithm on (D, S ∪{h}). Since h does not lie in any improving zone, the distribution algorithm will not change any of the state or auxiliary variable C(G), D(G), i.e., we will get ν(D, S ∪ {h}) = ν(D, S ) and consequently ω(D, S ∪ {h}) = ω(D, S ) in contradiction to our supposition.

If (9.5) is correct, h must be a center in Op (D, S ∪ {h}). Suppose without loss of generality that in the optimal solution Op (G), the center of the big interval C1 (G), lies to the left of h and that t centers in C(G) are located to the right of h. If t = 0 then ∀s ∈ C(G), h s and the conditions of Lemma 9.1.8 are satisﬁed. Since h does not lie in an improving zone we get from this lemma that ω(D, S ∪ {h}) = ω(D, S ) in contradiction to our supposition. Hence t must be at least 1.

Let Ci∗ (G) ∈ C(G) be the closest center which lies to the right of h. Di∗ (G) is the rightmost point that ∗ = max{h ∈ D | h Ci∗ (G) − rp (G)} be the closest point to the left which Ci∗ (G) Ci ∗ (G) covers. Let h does not cover. Since h does not lie in the improving zone of Ci∗ (G), d(h, Di∗ (G)) rp (G), so Di∗ (G) must be covered by a center which lies to the right of h. Since in Op (G) t centers are needed to cover DDi∗ (G), from Observation 9.1.3 there are at least t centers in Op (D, S ∪ {h}) which cover DDi∗ (G), all of which do not lie to the left of Ci∗ (G). This means that at most p − t centers in C(D, S ∪ {h}) are to the left of Ci∗ (G). In Op (G) p − t centers cover Dh∗, all of which lie to the left of h. These p − t centers are equal to the centers of Op−t (Dh∗, S ), since C1 (G) h. Moreover, the state variables of Op−t (Dh∗, S ) are equal to the p − t state variables of Op (G) corresponding to the p − t leftmost centers, so h does not lie in an improving zone of Op−t (Dh∗, S ). In this way the conditions of Lemma 9.1.8 applied on Op−t (Dh∗, S ) are satisﬁed.

Since h does not lie in an improving zone we get from this lemma that again ω(D, S ∪ {h}) = ω(D, S ) in contradiction to our supposition.

Since the conditions stated in Lemmas 9.1.7 and 9.1.9 rely on D0 (D, S ), rp (D, S ), Ci (D, S ), Di (D, S ) for i = 1,..., p we get from the same arguments used to prove Corollary 9.1.6

We are ready to prove Theorem 9.1.11 The discrete p-center problem on the line is a (p + 1, p)-dimensional discrete LP-type problem (D, S, ω) (ω is deﬁned in (9.4)) which satisﬁes the Violation Condition.

Proof: We ﬁrst note that since the ﬁrst coordinate of ω is rp (D, S), the solution of (D, S, ω) is a solution for the discrete p-center problem on the line as deﬁned in (9.2).

We need to show that both Monotonicity and Locality Conditions as well as the Violation Condition are satisﬁed. The Monotonicity Conditions follow from Observation 9.1.2. In order to show that the Locality of Demand Condition is satisﬁed we need to show that any S ⊆ S and any D ⊆ D ⊆ D where

implies ω(D ∪ {h}, S ) ω(D, S )). Let Op (D, S ) = (OD, OS ) be the solution of (ω, D, S ) (and due to (9.6 it is also the solution of (D, S, ω)) so

holds, then ω(D ∪ {h}, S ) ω(D, S ). Due to (9.6),(9.8), (9.10) and the Locality of Demand Condition we get that ω(OD ∪ {h}, S ) ω(D, S ). We conclude by using (9.9).

We show that the Locality of Supply Condition and the Violation Condition of Supply are satisﬁed in a similar way by using Corollary 9.1.10 instead of —Corollary 9.1.6.

Due to the deﬁnition of ω and the general position assumption, we note that Op (D, S ) is the only basis for G = (D, S ). Obviously the combinatorial dimension is (p + 1, p).

Remark. We note that if ω is deﬁned by (9.2) instead of (9.4) it may not satisfy either of the Locality Conditions. For instance, for p = 2 let D = {1, 5, 12} and S = {3, 7, 15}. We realize ω(D, S ) = 3 by locating the centers at 3 and 15. Let D = {5, 12} and h = 9. ω(D, S ) = ω(D, S ) = 3, ω(D ∪{h}, S ) = 6 but ω(D ∪ {h}, S ) = 3 by locating the centers at 7 and 15, so the Locality of Demand Condition is not satisﬁed. The Locality of Supply Condition is not satisﬁed in the following example. Let p = 2, D = {3, 9, 16}, S = {1, 6, 12}, S = {1, 12} and h = 18. We have ω(D, S ) = ω(D, S ) = 4, ω(D, S ∪ {h}) = 3 (by locating the centers at 6 and 18) but ω(D, S ∪ {h}) = 4.

For every non-trivial instance (D, S) for the discrete p-center problem (i.e., D = ∅ and |S| p), due to the ﬁniteness of the cardinalities of D and S we are guaranteed that (D, S) is feasible and bounded (i.e., the radius is between 0 and maxD − minD ) so by using Corollary 4.2.4 we get the following Helly theorem ** Lemma 9.1.**

12 For every instance (D, S, ω) of the discrete p-center problem (ω is deﬁned in (9.4)) and every r ∈ I +, H = (D, S) has the property rp (H) ≤ r if and only if every BD ⊆ D with |BD | ≤ p + 1 R has the property rp (BD, S) ≤ r. (Trivially, H has the property rp (H) ≥ r if and only if every BS ⊆ S with |BS | ≤ p has the property rp (D, BS ) ≥ r.) and changing every point h ∈ D to a unit interval centered at h we get Choosing r = 2

This result is a special case of the following theorem (which is a folklore) Theorem 9.1.14 Let D be a family of intervals on the real line and S be a set of points. If every p + 1 intervals of D are p-pierceable by points in S then D is p-pierceable by points in S.

The proof of this theorem relies on its corresponding continuous Helly theorem, Theorem 2.1.2(ii). We transform every interval h ∈ D into the maximum length interval t(h) which is contained in h and has end points in S. Let t(D) = {t(h) | h ∈ D}. We conclude by observing that D is p-pierceable by points in S if and only if t(D) is p-pierceable by points in S and by using Theorem 2.1.2(ii).

AS noted in the beginning of this subsection, we formulated here the discrete p-center problem on the line (p 1) as a ﬁxed-dimensional discrete LP-type problem, in a direct way. We do not use the connection between the discrete Helly theorems and discrete LP-type problems (Theorem 5.2.3) since the s-Helly number is p and not 1.

9.1.3 A linear time algorithm We use the algorithm in Section 6.3.3. Due to Theorem 6.3.6 and Theorem 9.1.11 above, the algorithm correctly solves the problem in randomized linear time when the violation test and basis calculation primitives

**run in constant time. It remains to show that these primitives can be implemented eﬃciently. Let:**

tvD be the time needed for checking whether a given d-element violates a given basis B.