FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:     | 1 |   ...   | 12 | 13 || 15 | 16 |   ...   | 27 |

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

-- [ Page 14 ] --

where rbtp (VG ) is defined in (8.7) and rbtp−1 (G) is defined in (8.1).

We formulate the p-Recovery Points problem on the real line as a p-dimensional dual LP-type problem as follows. Let Λ = I p ∪ {−∞, ∞} and let 2H denote the set of all induced subtrees of H. We define an R abstract problem (H, τp ) with a lexicographic objective function τp : 2H →Λ whose first p − 1 coordinates consist of the objective function ωp−1 defined in (8.3), and the last coordinate is the only leaf in H

–  –  –

Theorem 8.3.

1 The p-Recovery Points problem on the real line is a p-dimensional dual LP-type problem.

Proof: Let us consider the lexicographic function τp as defined in (8.10). Due to (8.9) its first coordinate is the roll-back time of the p-Recovery Points problem on the Real Line. Hence it is sufficient to show that the abstract problem (H, τp ) is a p-dimensional dual LP-type problem.

We conclude the proof by noting that the abstract problem (VH, − max VH ) is a 1-dimensional dual LPtype problem, and that due to Theorem 8.2.7 the abstract problem (H, ωp−1 ) is a (p − 1)-dimensional dual LP-type problem.

We could have solved (H, τp ) by applying Theorem 8.2.8 on the path tree H defined above. There is one problem with this approach. Since the real points in the given set VH are not sorted a-priori, it takes O(n log n) time to calculate (preprocess) the corresponding set of edges EH. Thus in this approach the preprocessing phase takes O(n log n) time, and the second phase of placing p-Recovery Points on the (path) tree H takes additional linear time, making this approach run in O(n log n) time.

In order to obtain a linear time solution, we give below specific linear time implementations for the various functions and algorithms that we defined in Section 8.2 for trees.

For every i we implement the distance to the root function drH, by setting drH (hi ) = hi − h1. For every i, j we implement the nearest common ancestor function ncaH, by setting ncaH (hi, hj ) = min{hi, hj }, and implement the distance function dH, by setting hi − hj if hi hj or h1 = hj = h1 dH (hi, hj ) = ∞ otherwise.

The general position assumption of the tree case that the finite lengths of the directed paths between pairs of vertices are all distinct, is equivalent in the real line case to assuming that no two distinct pairs of points in VH have the same distance. We note that all our results remain valid when we omit this general position assumption, by replacing the distance function dH with the lexicographic distance function d (x, y) = (dH (x, y), min{x, y}).

Let G = (VG, EG ) be an induced subtree of the path tree H. Let us consider an optimal solution, Op−1 (G), for (8.1) on G (which equals (8.7) on VG ). If there is more than one optimal solution with the same roll-back time, we take the one which is realized as follows. Due to the general position assumption, the big paths in all of the optimal solutions are identical and equal [hjl, hjh ]. Let nh be the number of recovery points on the path [hjh, h1 ], which are different from hjh. Let nl be the number of recovery points on the path [h2, hjl ], which are different from hjl and h2. Clearly nh + nl + 3 ≤ p.

We are now ready to define a distribution algorithm, that assigns correctly values to the state variables Ci (G), Di (G), i = 0,..., p. Intuitively, the algorithm “pushes” the recovery points as much as possible towards the middle of the big path. We let C1 (G) = h1 and D1 (G) = 0. For i = 2,..., nh we recursively define Ci (G) = max{v ∈ VG | v ≤ Ci−1 (G) + rbtp (G)} and Di (G) = rbtp (VG ) − (Ci (G) − Ci−1 (G)).

We let Cnh +1 (G) = hjh and Dnh +1 (G) = rbtp (VG ) − (Cnh +1 (G) − Cnh (G)). We let Cnh +2 (G) = hjl.

We let Cnh +3 (G) = min{v ∈ VG | v ≥ h2 − rbtp (VG )} and Dnh +3 (G) = rbtp (VG ) − (h2 − Cnh +3 (G)).

For i = 1,..., nl − 1 we recursively define Cnh +3+i (G) = min{v ∈ VG | v ≥ Cnh +2+i (G) − rbtp (VG )} and Dnh +3+i (G) = rbtp (VG )− (Cnh +3+i (G)− Cnh +2+i (G)). Let P = nh + nl + 3 be a variable holding the number of currently used recovery points (so CP −1 (G) is the recovery point closest to hjl from the right side). If P p we say that there are free recovery points. Last, we let Dnh +2 (G) = rbtp (VG )−(CP −1 (G)−Cnh +2 (G)).

If P p we set for every P i ≤ p, Ci (G) =“undefined” and Di (G) = −∞ (see Figure 8.2).

–  –  –

Figure 8.2: 9 recovery points and their corresponding “C” state variables.

Here nh = nl = 3.

Observation 8.3.2 The algorithm stated above, applied on input VG, hjh, hjl, rbtp (VG ), p, runs in O(pn) time and assigns to the state variables the same values as Procedure Main Distribute(G, hjh, hjl, rbtp−1 (G), p−

1) assigns.

It remains to show how to apply the randomized algorithm of [SW92] in order to solve this problem in linear time. We need to start with an initial basis (candidate basis) B0, for H as we do in Function Main Recovery below. This function returns a basis for H for the Recovery Points problem on H, and uses Function lptype from the algorithm of [SW92] (see Section 6.2).

Function Main Recovery(H, p) begin calculate h1 and h2, the minimal and maximal elements in VH choose a subset VH ⊆ VH with h1, h2 ∈ VH and |VH | = p at random calculate the roll-back time of VH by finding the maximal distance between consecutive points in VH find the two points hjh, hjl between which the big interval lies compute the state variables by executing the distribution algorithm presented above let B0 be the set consisting of the recovery points of VH return lptype(H, B0 ) end Recovery

–  –  –

.p current number of cuts on the xi axis.

.index always equals to i.

.length maximum length in axis xi after performing optimal.p guillotine cuts.

.worse maximum length in axis xi after performing optimal (.p − 1) guillotine cuts.

We also define the following two trees, sorted by two different keys:

LEN GT HT REE contains A[1],A[2],...,A[d] sorted by decreasing.length order (such that the root has the biggest length value). (The key of this tree is.length).

W ORSET REE contains A[1],A[2],...,A[d] sorted by increasing.worse order (such that the root has the smallest worse value). (The key of this tree is.worse).

We use the following three procedures on these two trees:

Root(t) returns the value of the key of the root of the tree t.

Insert(rec, t) inserts the record rec into the tree t while keeping the order of the tree.

Update(rec, t) deletes the root of the tree t and the performs Insert(rec, t).

We note that Function Root(t) can be implemented in constant time while Function Insert(rec, t) and Function Update(rec, t) can be implemented in O(log d) time ([CLR90]). We solve the p-Guillotine Cuts

problem by the following function:

–  –  –

8.4 Placing recovery points on circles In the p-Recovery Points problem on circles we are given a finite family H of points on a circle of perimeter l. We wish to find a subset H ⊆ H of p points that realizes the minimum of the largest interval length, resulted by cutting the circle at the points of H. We emphasis that the given points are not sorted, so constructing a circular graph from the input points requires Ω(n log n) time. We prove that solving the 2-Recovery Points problem on circles requires Ω(n log n) operations under the algebraic computation tree model (i.e., prove Theorem 5.1.7). We first define the following two problems

–  –  –

and Problem: l-distance Input: A finite family H of reals such that maxH − minH = 2l.

Output: “true” if and only if there are two points h1, h2 ∈ H (not necessarily adjacent), which are at distance l apart.

We will also use Theorem 8.4.1 (Ben-Or [Be83]) Any algebraic decision tree algorithm that solves the Membership in P ⊂ I n problem must have depth of at least log #(P ), where #(P ) is the number of disjoint connected components R of P.

Proof: (of Theorem 5.1.7) Let us consider an instance H = {h1,..., hn } of the l-distance problem as a single point (h1,..., hn ) ∈ I n. Let P be the set of points in I n for which the answer for the problem is “false”.

R R Every two points hi, hj divide I n into the three disconnected open subspaces xi xj + l, |xi − xj | l and R xj xi + l by the two hyperplanes xi = xj + l and xj = xi + l (xi and xj are the i’th and j’th coordinates in I n, respectively). In this way P is composed out of 3n disconnected regions. By Theorem 8.4.1 the decision R tree algorithm which solves the Membership in P problem is of depth Ω(log(3n )) = Ω(n log n), so under the algebraic computation tree model, it takes Ω(n log n) comparisons to solve the l-distance problem.

We conclude our proof by reducing the l-Distance problem to Placing 2-Recovery Points on Circles.

Having an instance H of the l-distance problem, we “connect” min H to max H and result a circle of perimeter 2l. This is done in constant time. We then solve the 2-Recovery Points problem on Circles. The answer for the l-distance problem is “true” if and only if the answer for the 2-Recovery problem is “true”.

Remark: It is possible to solve the p-Recovery Points problem on circles in O(n log n) time by first sorting the points in O(n log n) time and then applying the ideas of Frederickson and Johnson [FJ83].

Chapter 9 p-center problems

–  –  –

We note that the discrete abstract problem (D, S, rp ) is a p-supply problem (see Definition 3.3.17). As before, in the general discrete non-weighted p-center problem (the general discrete p-center problem, in short) all the weights equal 1.

The discrete weighted (non-weighted) p-center problem is a special case where S = D. We note that the radius of the continuous weighted (non-weighted) p-center on a given set H is not greater than the one of the discrete weighted (non-weighted) p-center on H, respectively.

9.1 p-center problems on the line In the p-center problem on the line the space is I and the distance function is ∀x, y ∈ I d(x, y) = |x − y|.

R R, For both discrete and continuous 1-center problems and for the continuous 2-center problem there are trivial O(n) time algorithms [Han73]. If the order of the demand points in D is given a-priori, the continuous pcenter problem can be solved in linear time by the fairly involved technique of Frederickson [Fr91]. Otherwise (the order of the points in D is not given), this problem can be formulated as a fixed-dimensional LP-type problem, P1, by using Theorem 2.1.2(ii) and by defining explicitly a lexicographic objective function. We note that by formulating the lexicographic Helly theorem, Theorem 2.3.4(ii), as a Helly system with a finite lexicographic Helly number, and using either Theorem 5.3.6 or Theorem 5.3.7, we can formulate the p-center problem as a fixed-dimensional LP-type problem, P2. In this way, any of the resulted problems P1, P2 is solvable in randomized linear time, for any fixed p, by using the various LP-type algorithms.

In the following subsections we formulate the general discrete p-center problem on the line as a fixeddimensional discrete LP-type problem and solve it in randomized linear time (for any fixed p 1). We are unaware of any other linear time solutions for this problem, even for the case p = 2. It is hard to see how we can use our linear time solution for the Recovery Points problem on the real line (Section 8.3), in order to solve the general discrete p-center problem on the line (even if we restrict two of the centers to be minS, maxS and let D = S).

Whenever it is clear from the context (i.e., when the input is two sets D, S), we will call the problem of calculating (9.2) discrete p-center.

9.1.1 A formulation as a discrete abstract problem (D, S, ω) Let D = {d1,..., dn } be a set of n demand points and S = {s1,..., sm } be a set of m supply points. To simplify the discussion, we assume general position of the points - all distances between demand points and supply points are distinct. Later on we will show how to remove this supposition. Let D ⊆ D and S ⊆ S be arbitrary non-empty sets and let G = (D, S ). Without loss of generality we assume that the optimal radius r = rp (D, S ) = d(d1, s1 ) is the distance between d1 and s1. If di ∈ D is at distance at most r from sj ∈ S we say that sj covers di since an interval of length 2r centered at sj covers di. Let c = d1 +s1 be the middle point between s1 to d1.

Let us consider an optimal solution for the discrete p-center problem on G with radius r = rp (G)1.

We define for it an optimal solution, not necessarily identical, which minimizes additional parameters as 1 In doing so we slightly abuse our notation since rp (G) = rp ((D, S )) while we refer to it as rp (D, S ) explained below. We start by defining the following state variables. C(G) = {C1 (G), C2 (G),...Cp (G)} is a set consisting of the at most p centers from S. For each Ci (G) ∈ S we define a corresponding state variable, Di (G) ∈ D which contains the farthest demand point which is served by Ci (G) and lies on the side of Ci (G) which doesn’t contain c (i.e., Ci (G) lies in the interval connecting between c and Di (G)). We also define the auxiliary variables C 1 (G),..., C p (G), D0 (G), D1 (G),..., Dp (G). The state and auxiliary variables are given values as follows. Due to the general position assumption, the radius r is realized uniquely by d1 and s1. Let nl be the number of centers to the left of (smaller than) s1 and nr be the number of centers to the right of (greater than) s1. Clearly nl + nr + 1 ≤ p. We let C1 (G) = s1, D0 (G) = d1. If nl ≥ 1 we let D2 (G) = min{h ∈ D }. For i = 2,..., nl, we recursively define Ci (G) = max{h ∈ S | h ≤ Di−1 (G) + r} and Di+1 (G) = min{h ∈ D | h Ci (G) + r}. We define Cnl +1 (G) = max{h ∈ S | h ≤ Dnl (G) + r}.

We let Dnl +2 (G) = max{h ∈ D }. For i = 1,..., nr, we recursively define Cnl +1+i (G) = min{h ∈ S | h ≥ Dnl +1+i (G) − r} and Dnl +2+i (G) = max{h ∈ D | h Cnl +1+i (G) − r}. We let P = nh + nl + 1 be a variable holding the number of center points in Op (G) (so CP (G) is the center closest to s1 which is bigger than s1 ).

Pages:     | 1 |   ...   | 12 | 13 || 15 | 16 |   ...   | 27 |

Similar works:

«1 Dissertationsschrift: Im Zeichen des „Tankdrachen“. Die Kriegführung an der Westfront 1916-1918 im Spannungsverhältnis zwischen Einsatz eines neuartigen Kriegsmittels der Alliierten und deutschen Bemühungen um seine Bekämpfung zur Erlangung des akademischen Grades doctor philosophiae (Dr. phil.) vorgelegt von Alexander Fasse Einschreibenummer: 505040 an der Philosophischen Fakultät I der Humboldt-Universität zu Berlin. Erstgutachter: Prof. Dr. Rolf-Dieter Müller Zweitgutachter:...»

«The Puzzle of the Prayer: A Study of John 17 Judith A. Diehl Doctor of Philosophy University of Edinburgh Declaration I declare that this thesis has been composed by me, it represents my own research and that it has not been submitted for any other degree or professional qualification. Judith A. Diehl ii Dedication This doctoral thesis is dedicated to my husband, Dave, without whom it could never have been completed, and to all our friends and family who supported this effort with their...»

«Archaeological geophysical prospection in peatland environments Kayt Armstrong Dissertation submitted in partial fulfilment of the requirements for the degree ‘Doctor of Philosophy’, awarded by Bournemouth University Volume 1 of 2 This copy of this thesis has been supplied on the condition that anyone who consults it is understood to recognise that copyright rests with its author and due acknowledgement must always be made of the use of any material contained in, or derived from, this...»

«A CASE STUDY OF EXTENDED DISCOURSE IN AN ASL/ENGLISH BILINGUAL PRESCHOOL CLASSROOM RAYCHELLE L. HARRIS A DISSERTATION Submitted to the Department of Education and the Graduate School of Gallaudet University in partial fulfillment of the requirements for the degree of Doctor of Philosophy December, 2010 This is to certify that the dissertation entitled: A CASE STUDY OF EXTENDED DISCOURSE IN AN ASL/ENGLISH BILINGUAL PRESCHOOL CLASSROOM prepared by Raychelle L. Harris is approved in partial...»

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

«CREATION, VALIDATION, AND ANALYSIS OF A NOVEL MODEL FOR THE STUDY OF NONADHERENCE IN NEWLY DIAGNOSED EPILEPTIC RATS by Kyle Edmond Thomson A dissertation submitted to the faculty of The University of Utah in partial fulfillment of the requirements for the degree of Doctor of Philosophy Department of Bioengineering The University of Utah December 2014 Copyright © Kyle Edmond Thomson 2014 All Rights Reserved The University of Utah Graduate School STATEMENT OF DISSERTATION APPROVAL The following...»

«Optical analysis of synaptic plasticity in rat hippocampus Inauguraldissertation zur Erlangung der Würde eines Doktors der Philosophie vorgelegt der Philosophisch-Naturwissenschaftlichen Fakultät der Universität Basel von Yan-Ping Zhang aus Shanghai, China Basel, 2008 Genehmigt von der Philosophisch-Naturwissenschaftlichen Fakultät Auf Antrag von Prof. Dr. Markus A. Rüegg Dr. Thomas G. Oertner Prof. Dr. Andreas Lüthi Prof. Dr. Carl Petersen Basel, den 11. 12. 2007 Dekan Prof. Dr....»



«© Lodi Nauta, in The Cambridge Companion to Boethius, ed. John Marenbon (Cambridge: Cambridge University Press, forthcoming) The Consolation: The Latin Commentary Tradition: 800-1700 Lodi Nauta Introduction ‘There is nothing superfluous in such a perfect work as the Consolation written by such a perfect philosopher as Boethius’.1 These words, written by the twelfth-century master William of Conches, express a sentiment which was almost universally shared by readers and commentators in the...»

«Jesus Came Healing and Curing By Ken A. Bryson Ph.D. Emeritus Professor of Philosophy Cape Breton University Sydney, Nova Scotia Canada B1P 6L2 E-mail ken_bryson@cbu.ca Abstract Jesus came primarily to forgive sins but on occasion, he cured the sick. Healing provides the greater good since it restores the relationship between Christ and us. Curing reverses the organism’s cellular degeneration, but is not necessary for salvation. While Jesus performs many miracles, he does not impose his will...»

«Issues in Leadership: A Study of Select Shakespearean Tragedies A Thesis Submitted in Partial Fulfillment of the Requirements for the Award of the Degree of Doctor of Philosophy in the Department of Humanities and Social Sciences Submitted by Shahida Roll No: 508HS303 Under the Supervision of Dr. Seemita Mohanty Associate Professor and Head Department of Humanities and Social Sciences National Institute of Technology, Rourkela Department of Humanities and Social Sciences National Institute of...»

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