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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |   ...   | 27 |

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

-- [ Page 18 ] --

A special case of Problem 10.2.1 is when the line transversal must be non-descending Problem 10.2.2 Given are a set D = {d1,..., dn } of (non necessarily pairwise disjoint) axis-parallel compact rectangles, and a set S = {s1,..., sm } of allowed line directions. Find the minimal scaling factor λ∗ = 1 λ1 (D, S) ∈ I +, such that λ∗ D admits a non-descending line transversal whose direction is in S.

R 1 The solution of Problem 10.2.1 is the minimum scaling factor between the solution of Problem 10.2.2 and the analogue problem where the line transversal must be non-ascending.

10.2.1 A formulation as a discrete LP-type problem In this subsection we formulate Problem 10.2.2 as a ﬁxed-dimensional discrete LP-type problem by using Theorem 2.4.

4 and Theorem 5.3.6.

Let G = (D, S ) ∈ 2D × 2S be an arbitrary set such that G = (∅, ∅). We ﬁrst look closely at an optimal solution for Problem 10.2.2 on G. Let λ∗ be the optimal scaling factor. Due to Theorem 2.2.9 there is a direction s∗ ∈ S and a set D ⊆ D of at most 4 rectangles such that the solution of Problem 10.2.2 on (D, {s∗ }) is λ∗.

For this solution we deﬁne the following variables:

–  –  –

• SLmin(D, S ) is the slope of the line transversal for λ∗ D with a minimal non-negative slope.

• SLmax (D, S ) is the slope of the line transversal for λ∗ D with a maximal non-negative slope.

(Due to the optimality of the scaling factor, the slope range does not contain any direction from S in its interior.) We are ready to deﬁne a lexicographic version for Problem 10.2.2 Problem 10.2.3 Given are a set D = {d1,..., dn } of (not necessarily pairwise disjoint) axis-parallel rectangles, and a set S = {s1,..., sm } of allowed line directions. Find the lexicographically minimal vector λ = (λ1, s, b, slmin, −slmax ), such that the line y = sx + b (s ∈ S) is non-descending, intersects all the rectangles in λ1 D, and the slope range corresponding to λ1 D is [slmin, slmax ].

–  –  –

Proof: We need to show that ∀ α, β ∈ Λ with α β, hα ⊆ hβ, i.e., for all x ∈ hα, x is also in hβ. This is true by monotonicity: a line transversal for αh with a slope in a speciﬁc slope range is also a line transversal for βh with a slope in the same range.

For every h ∈ S and λ ∈ Λ we let

–  –  –

We show now that actually the d-dimension is only 4. Due to Corollary A.3.1 each of the two endpoints of the slope range corresponding to λ∗ D, SLmin(G) and SLmax (G), are deﬁned by at most two rectangles (a deﬁning pair). BD must contain such two deﬁning pairs. Since DIR(G) is one of the boundary points of the slope range, any two such deﬁning pairs also deﬁne λ1 (G), DIR(G) and b(G). In this way BD consists only of two such deﬁning pairs, i.e., of at most 4 rectangles, and BS = DIR(D, S ).

Before we continue, we explain the values the decision and optimization problems return. The decision problem returns “yes” if and only if λ∗ = λ1 (D, S) ≤ 1. The optimization problem returns the minimal scaling factor λ1 (D, S), the minimal non-negative direction from S such that λ1 (D, S) admits a line transversal with direction DIR(D, S) and intersection point b(D, S) with the y axis, the slope range deﬁned by SLmin(D, S), SLmax (D, S), and a basis B = (BD, BS ) for (D, S). We note that there exist line transversals for λ∗ D with each of the slopes SLmin(D, S) and SLmax (D, S). We can view B and LIN E(D, S) as witnesses for the optimality of the scaling factor λ1 (D, S). We only need to check that λ1 (BD, S) = λ∗ (the Monotonicity of Demand Condition implies λ∗ (D, S) ≥ λ∗ ) and that the line transversal LIN E(D, S) intersects each one of the rectangles λ∗ h, h ∈ D (the Monotonicity of Supply Condition implies λ∗ (D, S) ≤ λ∗ ).

The ﬁrst test can be executed in |S| time and the second in |D| time.

10.2.2 A linear time algorithm In this subsection we apply the linear time algorithm stated in Section 6.3.3. We need to show that the conditions of Theorem 6.3.6 are satisﬁed, and implement each of the violation test and basis calculation primitives in constant time. In the last subsection we formulated Problem 10.2.2 as a (4, 1)-dimensional discrete LP-type problem. In order to show that the algorithm stated in Section 6.3.3 is correct it remains to show Lemma 10.2.5 (D, S, ν) meets the Violation Condition (Deﬁnition 3.3.15).

Proof: We need to show that for every (D, S ) ∈ 2D × 2S and (D, S ) ∈ 2D × 2S with ν(D, S ) =

ν(D, S ) the following properties hold:

1. For every h ∈ D, if ν(D ∪ {h}, S ) ν(D, S ) then ν(D ∪ {h}, S ) ν(D, S )

2. For every h ∈ S, if ν(D, S ∪ {h}) ν(D, S ) then ν(D, S ∪ {h}) ν(D, S ).

Let λ1 = λ1 (D, S ) = λ1 (D, S ). We deﬁne the following functions related to P (λ1 D ), the set of line transversal which λ1 D admits (see Corollary A.3.1 for the deﬁnition and structure of P (λ1 D ) in the dual space of line transversal). Let lmin (D, S ) be the only line transversal with direction SLmin(D, S ) that λ1 (D, S )D admits. Let bmin(D, S ) be its intersection point with the y-axis. In this way (SLmin(D, S ), bmin (D, S )) is the leftmost point in P (λ1 D ). We deﬁne lmax (D, S ) and bmax (D, S ) similarly, so (SLmax (D, S ), bmax (D, S )) is the rightmost point in P (λ1 D ).

The proof of both properties relies on the following observation which is true due to (10.2).

the functions SLmin, bmin, lmin, SLmax, bmax and lmin ν(D, S ) = ν(D, S )→ (10.3) have the same values on (D, S ) and on (D, S ).

We ﬁrst show that the ﬁrst property holds. h ∈ D violates (D, S ) if and only if the set of line transversals which λ1 h admits does not contain both lines lmin (λ1 D, S ) and lmax (D, S ) (i.e., {(SLmin(D, S ), bmin (D, S ));

(SLmax (D, S ), bmax (D, S ))} ⊂ P (λ1 h)). Using (10.3), the latter condition occurs if and only if the set / of line transversals which λ1 h admits does not contain both lines lmin (λ1 D, S ) and lmax (D, S ), which in its turn occurs if and only if h ∈ D violates (D, S ).

Regarding the second property, we observe that h ∈ S violates (D, S ) if and only if either the slope h lies in the interior of the slope range corresponding to λ1 D (so the scaling factor decreases), or h is the left endpoint of the slope range with h DIR(D, S ). We conclude the proof by using (10.3) again.

We are ready to make the complexity calculations. Given a basis B = (BD, BS ) and its optimal scaling factor λ1, we compute in constant time the functions SLmin (B), bmin (B), lmin (B), SLmax (B), bmax (B), lmin (B), DIR(B) and the set of all line transversals for λ1 B, P (λ1 BD ) = ∩h∈BD D(λ1 h) (see Corollary A.3.1 for the notations).

The following violation tests are implemented in constant time as follows tvS : A new s-element h violates B if and only if either h lies in the interior of the slope domain (SLmin (B), SLmax (B)), or h = SLmin(B) and DIR(B) = SLmax (B).

tvD : A new d-element h violates B if and only if D(λ1 h) does not contain {(SLmin(D, S ), bmin (D, S ));

(SLmax (D, S ), bmax (D, S ))}.

the basis calculation for (D, S ) where both |D |, |S | are constants can be implemented in constant time as follows. For every h ∈ S calculate the minimal scaling factor λ1 (D, {h}) (this can be done by projecting the rectangles in D on a line perpendicular to direction h as explained in the beginning of Section 10.2 for h being the vertical direction). Let the s-element part of a basis BS, be the set consisting of the minimal h ∈ S resulting the minimal such λ1 (D, {h}). In order to deﬁne a d-element part of a basis BD, calculate P (λ1 D ) = ∩h∈D D(λ1 h) and let BD consists of two pairs that deﬁne the leftmost and rightmost point in P (λ1 D ). Due to Corollary A.3.1, (BD, BS ) is a basis for (D, S ). We have proved Theorem 10.2.6 Problem 10.2.1 is solvable in (randomized) linear time.

10.3 Discrete case II - A ﬁnite number of allowed line transversals We now deﬁne another discrete version for the line transversal of axis-parallel rectangles optimization problem.

<

–  –  –

The corresponding decision problem is Problem 10.3.2 Given are a set D of axis-parallel rectangles and a set S of lines. Decide whether D admits a line transversal from S.

A corollary of Theorem 2.2.12 is that the Helly number corresponding to the above problem is unbounded.

We show here Theorem 10.3.3 Problem 10.3.2 requires Ω(n log n) time under the algebraic computation tree model (when m = n).

Proof: We reduce in linear time the set equality problem to Problem 10.3.2. Given an instance of the set equality problem, i.e., two sets A, B of n real numbers each, we act as follows. We ﬁnd minA and maxA (minB and maxB ), the minimal and maximal elements in A (B), respectively. We deﬁne two new sets A = { maxA − min)A − 1 | a ∈ A} and B = { maxB − minB − 1 | b ∈ B}. All the elements in A and B are 2(a−minA 2(b−minB ) numbers between -1 to 1 and A = B if and only if A = B. For any −1 ≤ r ≤ 1 let p(r) be the intersection point of the unit circle and the ray originating at the origin and having an angle of r radians with the positive part of the x-axis. We deﬁne two instances for Problem 10.3.2. The ﬁrst instance, Instance I, has a set of lines SI = S(A ) and a set of rectangles (intervals) DI = D(B ) deﬁned as follows. We let S(A ) = {s(a ) | a ∈ A } where s(a ) is the line tangent to the unit circle at point p(a ). We let D(B ) = {i(b ) | b ∈ B } where i(b ) is an horizontal interval of length 100, whose left end is slightly to the right of p(b ) (from a computation point of view we build the left end of the interval at exactly p(b) but symbolically do not include this point in the interval). The resulting construction looks similar to Figure 2.4 rotated by 1 π radians clockwise. From the above construction we get that D(B ) admits a line transversal from S(A ) if and only if A ⊂ B. The second / instance, Instance II, has the set of lines SII = S(B ) and the set of rectangles DII = D(A ). we get that D(A ) admits a line transversal from S(B ) if and only if B ⊂ A. We conclude the proof by observing that / A = B if and only if both instances of Problem 10.3.2 return negative responses.

Chapter 11 The simple stochastic game We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl [SW92] for LP-type problems, we obtain the ﬁrst strongly subexponential solution for SSG’s (a strongly subexponential algorithm has only been known for binary SSG’s [Lu95]). Using known reductions between various games, we achieve the ﬁrst subexponential solution for Discounted Payoﬀ Games. Our solution is in fact strongly subexponential. We also give alternate simple proofs for the best known upper bounds for Parity Games, Mean Payoﬀ Games and binary SSG’s.

11.1 Introduction In this chapter we use the LP-type framework in order to give the ﬁrst strongly subexponential solution for Simple Stochastic Games (deﬁned below). To the best of our knowledge, this is the ﬁrst application of the LP-type framework for solving a problem which is neither in computational geometry nor in location theory.

Moreover, it is the ﬁrst application of variable-dimensional LP-type problems.

A Simple Stochastic Game (SSG) is deﬁned on a directed graph with three types of vertices, min, max, and average, along with two sink vertices, the 0-sink and the 1-sink. The sink vertices have no outgoing edges. For every average vertex ak, the outgoing edges from ak have positive rational weights such that the sum of their weights is 1. The outgoing edges from the min and max vertices are unweighed. One of the vertices is a start vertex.

The game is a contest between two players, 0 and 1. It is played in the following way. Begin by placing a token on the start vertex. When the token is on a min vertex yj, player 0 moves it along one of the outgoing edges of yj. When the token is on a max vertex xi, player 1 moves it along one of the outgoing edges of xi.

When the token is on an average vertex ak, the edge along which the token is moved is determined randomly, in proportion to the weights of the edges outgoing from ak. The game ends when one of the sink vertices is reached. The goal of player 1 is to reach the 1-sink. The goal of player 0 is to avoid the 1-sink.

Before the game begins, player 1 chooses an outgoing edge from each max vertex. These selected edges will deﬁne a strategy for player 1. During the game, whenever the token is on a max vertex, player 1 will move the token along the edge that is included in his strategy. (Deﬁning strategies deterministically in this way does not result any loss of generality [Co92]). Similarly, a choice of an outgoing edge for each min vertex is a strategy for player 0. Given a SSG, we would like to ﬁnd the best strategies for both players. The corresponding decision problem is to determine whether player 1 wins with probability greater than 2 when both players use their “best strategies”.

A binary SSG is a special case of a SSG, where the outgoing degrees of the min and max edges are bounded by 2, and where all average vertices have exactly two outgoing edges of weight 2 each. Zwick and Paterson [ZP96] gave a simple polynomial reduction from a SSG with n vertices and nn edges, in which the denominators of all the (rational) probabilities are at most l, to a binary SSG with n = O((n + nn) log l) vertices and nn = O(nn log l) edges. We note that nn may be quadratic in n, so the number of vertices in the binary game resulted by the reduction,√, may be Θ(n2 ). In this case, the running time of the best n known algorithm for binary SSG’s (which is e n time) becomes exponential in n.

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |   ...   | 27 |

Similar works:

«Synthesis and Magnetic Properties of Cobalt Nickel Nanoparticles Prepared by Chemical Reduction Methods Jalpa Dipesh Patel Thesis submitted to the University of London, University College London in partial fulfilment of the requirements for the degree of Doctor of Philosophy In Chemistry Supervised by: Prof Ivan P. Parkin, Department of Chemistry, University College London Prof Quentin A. Pankhurst, London Centre for Nanotechnology, University College London June 2007 -1UMI Number: U592381 All...»

«Vicky Johnson Gatzouras Family Matters in Greek American Literature Doctoral Dissertation to be publicly discussed in English at Blekinge Institute of Technology, Karlskrona, Campus Gräsvik, Room 3248, on February 9 at 10:15, for the degree of Doctor of Philosophy Blekinge Institute of Technology School of Technoculture, Humanities and Planning and Göteborg University Department of English i © 2007 Vicky Johnson Gatzouras Printed by Kaserntryckeriet AB Karlskrona, January 2007 Sweden For my...»

«AFRICAN COASTAL ELITE ARCHITECTURE: CULTURAL AUTHENTIFICATION DURING THE COLONIAL PERIOD IN ANOMABO, GHANA By COURTNAY MICOTS 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 © 2010 Courtnay Micots To the gracious people of Anomabo – the leaders, families and individuals without whom this work would not have been possible History books begin and end, but the...»

«DEVELOPMENT OF A COMPUTER-AIDED FAULT TREE SYNTHESIS METHODOLOGY FOR QUANTITATIVE RISK ANALYSIS IN THE CHEMICAL PROCESS INDUSTRY A Dissertation by YANJUN WANG Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY December 2004 Major Subject: Chemical Engineering DEVELOPMENT OF A COMPUTER-AIDED FAULT TREE SYNTHESIS METHODOLOGY FOR QUANTITATIVE RISK ANALYSIS IN THE CHEMICAL PROCESS INDUSTRY A...»

«HIGH VELOCITY OUTFLOWS IN QUASARS By PAOLA RODR´ IGUEZ 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 c 2009 Paola Rodr´ ıguez To my mother, my family and my friends, because without their support I am nothing ACKNOWLEDGMENTS I was told long time ago that “es de buen nacido ser agradecido”. Como mi madre me educ´ muy bien, no puedo evitar intentar incluir...»

«© 2013 Susannah Kate Devitt ALL RIGHTS RESERVED HOMEOSTATIC EPISTEMOLOGY: RELIABILITY, COHERENCE AND COORDINATION IN A BAYESIAN VIRTUE EPISTEMOLOGY By SUSANNAH KATE DEVITT A Dissertation submitted to the Graduate School-New Brunswick Rutgers, The State University of New Jersey in partial fulfillment of the requirements for the degree of Doctor of Philosophy Graduate Program in philosophy written under the direction of Ernest Sosa and approved by New Brunswick, New Jersey OCTOBER 2013...»

«Proceedings of the 3rd Annual Hawaii International Conference on Arts and Humanities. Honolulu, HI, 2005: 5520-5527. Render Unto Caesar Douglas W. Shrader1 Distinguished Teaching Professor & Chair of Philosophy SUNY Oneonta Oneonta, NY Abstract. The first amendment to the U.S. Constitution sets forth a principle commonly known as “separation of church and state.” As obvious as the principle may seem to those who have grown up in its shadow, it is not without critics. There are many, for...»

«Community and the Habits of Democratic Citizenship: An Investigation into Civic Engagement, Social Capital and Democratic Capacity-Building in U.S. Cohousing Neighborhoods Lisa Dawn Poley Dissertation submitted to the faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy In Environmental Design and Planning Dr. Max O. Stephenson, Committee Chair Dr. Joyce Rothschild Dr. Cornelia Flora Dr. Heike Mayer...»

«Vol. 4, No. 1 The Pulse 1 LOCKE AND ROUSSEAU: EARLY CHILDHOOD EDUCATION By Jamie Gianoutsos Both John Locke (1632-1734) and Jean-Jacques Rousseau (1712-1778) write as early modern social contract theorists, and both promote reason and freedom as essential components of political societies. Yet these thinkers take many distinct, and at times opposing, stances on education. This paper will explore John Locke and Jean-Jacques Rousseau’s thoughts on early childhood education, first by considering...»

«CURRICULUM VITAE TONYA EDMOND, Ph.D. George Warren Brown School of Social Work Washington University in St. Louis Campus Box 1196 One Brookings Drive St. Louis, Missouri 63130-4899 314-935-8131 EDUCATION Doctor of Philosophy, School of Social Work, The University of Texas at Austin, Austin, Texas (1997). Dissertation topic: Eye Movement Desensitization and Reprocessing: Evaluating its effectiveness in reducing trauma symptoms in adult female survivors of childhood sexual abuse. Dissertation...»

«ABSTRACT Title of Dissertation / Thesis: BRED VECTORS IN THE NASA NSIPP GLOBAL COUPLED MODEL AND THEIR APPLICATION TO COUPLED ENSEMBLE PREDICTIONS AND DATA ASSIMILATION. Shu-Chih Yang, Doctor of Philosophy, 2005 Dissertation / Thesis Directed By: Professor Eugenia Kalnay, Department of Meteorology Professor Ming Cai, Florida State University The theme of my thesis research is to perform breeding experiments with NASA/NSIPP coupled general circulation model (CGCM) in order to obtain ENSOrelated...»

«COMPASSIONATE RESPONSES TOWARD VICTIMS: DO PERCEIVED INNOCENCE, PROXIMITY AND SERIOUSNESS MATTER? by YAN YAN SHUHUA ZHOU, COMMITTEE CHAIR KIMBERLY L. BISSELL JENNIFER D. GREER JAMES D. LEEPER LU TANG A DISSERTATION Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Journalism in the Graduate School of The University of Alabama TUSCALOOSA, ALABAMA i Copyright Yan Yan 2012 ALL RIGHTS RESERVED i ABSTRACT People have an innate tendency...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.