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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 27 |

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

-- [ Page 20 ] --

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.

–  –  –

Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 27 |

Similar works:

«Helly Theorems and Generalized Linear Programming by Annamaria Beatrice Amenta B.A. (Yale University) 1979 A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science in the GRADUATE DIVISION of the UNIVERSITY of CALIFORNIA at BERKELEY Committee in charge: Professor Raimund Seidel Professor John Canny Professor William Thurston Helly Theorems and Generalized Linear Programming Copyright 1993 by Annamaria Beatrice Amenta...»

«Causation and Culpability 1 Causation, Norm Violation and Culpable Control [forthcoming in the Journal of Philosophy] Mark D. Alicke Ohio University David Rose Carnegie Mellon University Dori Bloom Ohio University Causation and Culpability 2 Acknowledgements We would like to thank Josh Knobe, Chandra Sripada and Liane Young for their helpful comments on an earlier draft of this paper. We would also like to thank David Danks for his very helpful discussions. Causation and Culpability 3...»

«EXPLAINING REASONS: WHERE DOES THE BUCK STOP? BY ULRIKE HEUER JOURNAL OF ETHICS & SOCIAL PHILOSOPHY VOL. 1, NO. 3 | MARCH 2006 URL: WWW.JESP.ORG COPYRIGHT © ULRIKE HEUER 2006 JOURNAL OF ETHICS & SOCIAL PHILOSOPHY | VOL. 1, NO. 3 EXPLAINING REASONS: WHERE DOES THE BUCK STOP? Ulrike Heuer Explaining Reasons: Where Does the Buck Stop? Ulrike Heuer I T WOULD BE GOOD IF I could finally knock this paper into shape. That gives me a reason to sit down and work on it. Or is it the other way around? Is...»

«CURRICULUM VITAE Peter Godfrey-Smith January 2014 Philosophy Program, The Graduate Center City University of New York 365 Fifth Avenue New York, NY 10016, USA.CONTACT Phone: +1 (617) 462 8887 Email: pgodfreysmith@gmail.com BIOGRAPHICAL Born Sydney, Australia in 1965. Citizenship: Australia and US. Married, no children.ACADEMIC APPOINTMENTS 1991 to 1998: Assistant Professor of Philosophy, Stanford University. 1998 to 2003: Associate Professor of Philosophy, Stanford University. 2003 to 2005:...»

«A PERSONALIZED VIRTUAL ENVIRONMENT AS A TESTBED FOR ASSISTIVE TECHNOLOGIES by XIANGKUI YAO A DISSERTATION Presented to the Department of Computer and Information Science and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Doctor of Philosophy December 2011 DISSERTATION APPROVAL PAGE Student: Xiangkui Yao Title: A Personalized Virtual Environment as a Testbed for Assistive Technologies This dissertation has been accepted and approved...»

«Assessing Resilience in Preschool Children Exposed to Intimate Partner Violence: Utilizing Multiple Informants and Evaluating the Impact of the Preschool Kids‘ Club Intervention by Kathryn Helen Howell A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Psychology) in The University of Michigan Doctoral Committee: Professor Sandra A. Graham-Bermann, Chair Associate Professor Andrew C. Grogan-Kaylor Associate Professor Christopher Stephen...»

«Fostering Participation and Capacity Building with Neighborhood Information Systems by David L. Epstein A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Urban and Regional Planning) in the University of Michigan Doctoral Committee: Professor Margaret Dewar, Chair Professor Larry Gant Professor Jonathan Levine Professor June Manning Thomas © David L. Epstein 2015 Dedication To my mother, Judith Epstein, who instilled in me a hunger for...»

«PH.D. THESIS Air-Caching: Adaptive Hybrid Data Delivery by Konstantinos Stathatos Advisor: Nick Roussopoulos and John S. Baras CSHCN Ph.D. 99-1 (ISR Ph.D. 99-2) The Center for Satellite and Hybrid Communication Networks is a NASA-sponsored Commercial Space Center also supported by the Department of Defense (DOD), industry, the State of Maryland, the University of Maryland and the Institute for Systems Research. This document is a technical report in the CSHCN series originating at the...»

«Helsinki University of Technology Department of Industrial Engineering and Management Doctoral Dissertation Series 2010/5 Espoo 2010 IDENTIFICATION WITH VIRTUAL TEAMS Marko Hakonen Dissertation for the degree of Doctor of Philosophy to be presented with due permission of the Faculty of Information and Natural Sciences, Helsinki University of Technology, for public examination and debate on March 19, 2010, at 12 o’clock in Auditorium TU1 at University of Technology, Espoo, Finland. Helsinki...»

«On key modulators of higher-order chromatin structure Andr´ J. Faure e EMBL – European Bioinformatics Institute Magdalene College A dissertation submitted to the University of Cambridge for the degree of Doctor of Philosophy September, 2013 This dissertation is the result of my own work and includes nothing which is the outcome of work done in collaboration except where speciﬁcally indicated in the text. No part of this work has been submitted or is currently being submitted for any other...»

«To appear in the European Journal of Philosophy Benacerraf's Dilemma Revisited Bob Hale and Crispin Wright 1. The Dilemma One of the most influential articles1 in the last half century of philosophy of mathematics begins by suggesting that accounts of mathematical truth have been motivated by two quite distinct concerns: (1) the concern for having a homogeneous semantical theory in which the semantics for the statements of mathematics parallel the semantics for the rest of the language (2) the...»

<<  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.