WWW.THESIS.XLIBX.INFO FREE ELECTRONIC LIBRARY - Thesis, documentation, books

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 13 | 14 || 16 | 17 |   ...   | 27 |

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

-- [ Page 15 ] --

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.

Pages:     | 1 |   ...   | 13 | 14 || 16 | 17 |   ...   | 27 |

Similar works:

«A Mathematical Model of Dopamine Neurotransmission by David Tello-Bravo A Dissertation Presented in Partial Fulﬁllment of the Requirements for the Degree Doctor of Philosophy Approved May 2011 by the Graduate Supervisory Committee: Sharon M. Crook, Co-Chair Priscilla E. Greenwood, Co-Chair Steven M. Baer Edward Casta˜ eda n Carlos Castillo-Ch´ vez a ARIZONA STATE UNIVERSITY May 2012 ABSTRACT Dopamine (DA) is a neurotransmitter involved in attention, goal oriented behavior, movement, reward...»

«A CULTURAL ANALYSIS OF THE RUSSO-SOVIET ANEKDOT by Seth Benedict Graham BA, University of Texas, 1990 MA, University of Texas, 1994 Submitted to the Graduate Faculty of Arts and Sciences in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh UNIVERSITY OF PITTSBURGH FACULTY OF ARTS AND SCIENCES This dissertation was presented by Seth Benedict Graham It was defended on September 8, 2003 and approved by Helena Goscilo Mark Lipovetsky Colin...»

«The Living Documentary: from representing reality to co-creating reality in digital interactive documentary by Sandra Gaudenzi A thesis submitted for the degree of Doctor of Philosophy. Goldsmiths (Centre for Cultural Studies), University of London. London, January 2013. I hereby declare that this thesis is entirely my work Sandra Gaudenzi Date: Abstract This thesis concentrates on the emerging field of interactive documentaries. Digital interactive and networked media offer so many new...»

«STEVEN JAMES CRUM Department of Native American Studies University of California, Davis Davis, California 95616 (530) 752-3237 sjcrum@ucdavis.edu Tribal Enrollment: Shoshone-Paiute Tribes of the Duck Valley Indian Reservation, Owyhee, Nevada (7/8 degree Western Shoshone Indian). Education Doctor of Philosophy (History) University of Utah, Salt Lake City Ph.D. dissertation: “The Western Shoshone of Nevada and The Indian New Deal” December 1983 Master of Education University of Arizona,...»

«IDENTIFICATION AND QUANTIFICATION OF SUBMARINE GROUNDWATER DISCHARGE IN THE HAWAIIAN ISLANDS DISSERTATION SUBMITTED TO THE GRADUATE DIVISION OF THE UNIVERSITY OF HAWAI'I AT MĀNOA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN GEOLOGY AND GEOPHYSICS AUGUST 2012 By Jacque L. Kelly Dissertation Committee: Craig Glenn, Chairperson Paul Lucey Henrieta Dulaiova Brian Popp Aly El-Kadi Francis Sansone Keywords: Submarine groundwater discharge, Oahu, thermal...»

«MIXING LIGHT AND MATTER WAVES: PRINCIPLES AND APPLICATIONS By YUPING HUANG A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Physics and Astronomy UMI Number: 3381233 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper...»

«Two-dimensional Clay and Graphene Nanosheets for Polymer Nanocomposites and Energy Storage Applications A Dissertation SUBMITTED TO THE FACULTY OF UNIVERSITY OF MINNESOTA BY Yuqiang Qian IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Adviser: Andreas Stein August, 2013 © Yuqiang Qian 2013 Acknowledgements First, I would like to thank my research advisor, Prof. Andreas Stein, for his guidance, advice and support all throughout my graduate studies. I also owe...»

«Diplomarbeit Titel der Diplomarbeit Alchemie und Magie als Bindeglied zwischen Religion und Naturphilosophie bei Paracelsus im Labyrinthus medicorum errantium Verfasserin Regina Zikmund-Hochrather angestrebter akademischer Grad Magistra der Philosophie (Mag. phil.) Wien, 2012 Studienkennzahl lt. Studienblatt: A296 Studienrichtung lt. Studienblatt: Diplomstudium Philosophie Betreuer: Univ.-Doz. Mag. Dr. Sergius Kodera „Daß ich erkenne, was die Welt im Innersten zusammenhält.“ (Goethe,...»

«DIFFUSE OPTICAL TOMOGRAPHY: IMAGING MULTIPLE STRUCTURAL AND FUNCTIONAL FEATURES By RUIXIN JIANG A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA © 2012 Ruixin Jiang To my dear mom ACKNOWLEDGMENTS First, I would like thank Dr. Huabei Jiang, for his support and guidance during the past six years of my pursuit for the Ph. D. He brought me insights into the field of...»

«MP_C43.qxd 11/23/06 2:41 AM Page 353 Virtues and Happiness Boethius on the Supreme Good, or on the Life of the Philosopher Since in every kind of being there is a supreme possible good, and since man too is a certain species or kind of being, there must be a supreme possible good for man, not a good which is supreme in the absolute sense, but one that is supreme for man. The goods which are accessible to man are limited and do not extend to inﬁnity. By means of reason we will seek to...»