Bad Guys are Rare Probabilistic Analysis of an Elementary

Bad Guys Are Rare Probabilistic Analysis Of An Elementary-Free PDF

  • Date:20 Dec 2019
  • Views:50
  • Downloads:0
  • Pages:121
  • Size:1.09 MB

Share Pdf : Bad Guys Are Rare Probabilistic Analysis Of An Elementary

Download and Preview : Bad Guys Are Rare Probabilistic Analysis Of An Elementary


Report CopyRight/DMCA Form For : Bad Guys Are Rare Probabilistic Analysis Of An Elementary


Transcription:

Creating this thesis would have been much more inconvenient without great tools. as LATEX and its plethora of packages KOMA Script METAPOST GNU Emacs. GNU make CVS gnuplot and last but not least Perl,Acknowledgements. Although my name is the only one appearing on the title page a lot. of people have been directly or indirectly involved in the creation of. this thesis, First of all I want to thank my supervisors Prof Dr Martin. Dietzfelbinger and Prof Dr Sven O Krumke Thanks go to Martin. Dietzfelbinger for supporting my work at ZIB by giving me the op. portunity to work at the Studienarbeit and this thesis in Berlin He. and Prof Dr Manfred Kunde aroused my interest for this strange. theoretical stuff Sven O Krumke always directed and motivated. me providing help and discussions when I needed them. Im also very grateful to J rg Rambau Andreas Tuchscherer and. Tjark Vredeveld for reading a preliminary version of this thesis and. giving many hints and suggestions for improvements I really had a. hard time incorporating them, Further thanks go to Amin Coja Oghlan who kindly answered. any questions I had concerning the result that makes up the main. part of this thesis I am also indebted to Prof Dr Martin Gr tschel. for providing me with an opportunity to work as a trainee at ZIB. which was the starting point for my stay there I have to mention. my other colleagues from the Optimization Department who have a. part in the nice and inspiring atmosphere there, Last but not least I want to thank my parents and my girlfriend. Petra Gottstein for supporting my studies,2004 07 05 059 IN99 2239 iii.
iv 2004 07 05 059 IN99 2239,List of Algorithms vii. 1 Introduction 1, 1 1 Graph theoretic Interpretation of Dial a Ride Problems 2. 1 2 Offline Dial a Ride Problems State of the Art and New Results 3. 1 3 Online Dial a Ride Problems State of the Art and New Results 5. 1 4 Dial a Ride Problems on Trees 6,1 5 Overview on this Thesis 7. 2 A Fast Approximation Algorithm for the Dial a Ride Problem on. 2 1 Basic Idea Balancing Arcs 9, 2 2 Computing a Balancing Set of Arcs in Linear Time 13. 2 2 1 Computing the Balancing Defect b u v 14,2 2 2 Contracting Balancing Arcs 17.
2 2 3 Running Time of the Balancing Algorithm 19,2 3 Connecting Nontrivial Components 20. 2 4 A Special Case Where use MST is Optimal 23, 3 Probability Theory Basics for Probabilistic Analysis 27. 3 1 Basic Notions Random Objects and Random Variables 27. 3 2 Numerical Properties of Random Objects 31,3 3 Non numerical Properties of Random Objects 34. 4 Probabilistic Analysis of the Darp on Trees 37,4 1 Overview and Key Ideas 37. 4 2 A More Technical Road Map 39,4 3 Some Preliminaries 45.
4 4 Estimating the Number of Components Arising From Balancing Arcs 51. 4 5 The Structure of the Graph After Balancing 58,4 6 Algorithm use MST Is a a s Optimal 61. 5 Towards Probabilistic Competitive Analysis of the OnlineDarp on. 5 1 Online Versions of Darp 69, 5 2 Deterministic Competitiveness Results for OnlineDarp 72. 2004 07 05 059 IN99 2239 v, 5 3 Probabilistic Extensions Randomized and Probabilistic Competitive. Analysis 74,5 4 The Strategies Ignore and Replan 77. 5 5 Structure of Snapshot Problems 79, 5 6 Probabilistic Analysis of the High Load Case 81.
5 6 1 A Simple Special Case and Some First Observations 85. 5 6 2 There Are Many Requests Per Phase 86,5 6 3 Estimating the Number of Balancing Arcs 89. 6 Conclusions and Outlook 93,A Technical Preliminaries 95. A 1 Graph Theory 95,A 1 1 Basic Notions 95,A 1 2 Graphs and Metrics 96. A 1 3 Useful Facts 98,A 2 Asymptotics 99,A 3 Important Combinatorial Formulas 99. A 4 Complexity Theory Optimization vs Approximation 101. A 5 Results from Applied Probability 102,A 5 1 A Short Excursion to Queuing Theory 102.
A 5 2 A Result on the Symmetric Random Walk 103,A 6 Tools from Analysis 104. Bibliography 105,Zusammenfassung 109,Thesen 111,vi 2004 07 05 059 IN99 2239. List of Algorithms, 2 1 Algorithm Balance for determining a balancing set 13. 2 2 Algorithm compute b for computing b u v 16, 2 3 Algorithm balancing arcs up for computing contracted balancing. arcs directed towards the root 18, 2 4 Algorithm use MST for computing an approximate solution to the.
Darp on trees 24, 4 1 Algorithm NormalizeTree for transforming a tree T to a canonic. structure 46, 4 2 Algorithm PartitionUpperPart for partitioning the upper vertex. set of a tree T into segments 67,5 1 Ignore strategy 78. 5 2 Replan strategy 78,2004 07 05 059 IN99 2239 vii. viii 2004 07 05 059 IN99 2239,1 Introduction, In this thesis we study a certain simple problem from a general class of transportation.
problems known as Dial a Ride problems Dial a Ride problems abstract transporta. tion problems frequently arising in practice both in industrial and service applica. tions The basic setting is the following We control a set of servers which travel. along a transportation network Furthermore there are requests for transportation. i e our servers have to carry some goods or persons from a source location to a. destination Now we have to decide which requests to assign to each server and the. exact order of service such that a certain optimization criterion is met In general. there are some constraints to these decisions for example limited capacity of the. Real world applications covered by this general framework are for example. Berlin s Telebus Telebus is Berlin s transportation service for handicapped people. Handicapped persons may request to be transported at arbitrary times between. arbitrary locations These requests are collected a day in advance and shall be. scheduled to a fleet of vehicles mini busses which is rent on a day by day. basis Clearly the objective is to incur small cost for renting vehicles while. ensuring a punctual service In this case the transportation network is the road. network of Berlin See Bornd rfer et al 8 for details of how to tackle this. complex large scale problem, Commissioning in high rack warehouses High rack warehouses play an essential. role in modern logistics They are used to store and retrieve larger quantities of. many different goods Typically each high rack is operated by an elevator like. system where the elevator travels along a rectangular grid which constitutes. the transportation network Requests consist of a set of goods which have to be. commissioned into one packaging unit for delivery to customers A description. of a concrete high rack warehouse system can be found in Hauptmeier s Diplom. The focus of this thesis is more limited Many of the Dial a Ride problems arising. in practice feature complex constraints often interacting in a nontrivial way with. 2004 07 05 059 IN99 2239 1,1 Introduction, application specific issues The analysis of such intricate systems is very involved if. not intractable One therefore tries to consider simplified problems exhibiting the. essential features This theoretical approach is taken in this thesis. 1 1 Graph theoretic Interpretation of Dial a Ride, We now derive a formalization of Dial a Ride problems which will be the basis for. the further discussion This formalization is based on concepts from Graph Theory. see Section A 1 for a short introduction, To simplify our graph theoretic model and since we will later study a more spe. cialized version anyway we first make some further assumptions on the Dial a Ride. problems under consideration We assume that, There is only one server which can serve at most one request at a time.
All requests can be served by just traveling to a source location picking up the. object to transport and traveling to the destination location where the object. is delivered there are no other constraints, There is a distinguished location called depot from which the server unit starts. and has to return to, Once the service of a request has started there must not be an interruption. until the request is finished at the destination location non preemptive trans. There are only finitely many interesting locations i e source and destination. locations and we know the structure of the transportation network especially. the distances between the locations, The objective is the total completion time also known as makespan that is we. want to finish all requests as early as possible This is equivalent to minimizing. the total travel distance, These restrictions allow for the following abstract description Each location is. modeled by a vertex of a graph G V E whose edges are possible interconnections. between the locations Furthermore we use an edge length function c E R 0. assigning each edge the length of the corresponding interconnection A transportation. 2 2004 07 05 059 IN99 2239, 1 2 Offline Dial a Ride Problems State of the Art and New Results.
request is then simply an ordered pair or arc of locations A feasible transportation. is given by a directed closed walk sequence of arcs on the vertex set of our graph. which starts and ends at the depot vertex o V and traverses each request arc. exactly once Note that in order to obtain such a feasible transportation we may. have to add arcs connecting the destination location of a request with the source. location of the next one These arcs correspond to empty rides of the server Notice. that we do not allow splitting a request arc into successive arcs traversing one edge. each so the non preemptive transportations requirement will be fulfilled We call a. feasible transportation a tour or solution Our goal is to find a tour minimizing the. total travel distance Formally we have the following optimization problem. Definition 1 1 Dial a Ride Problem Darp, Instance A connected graph G V E called underlying network a multiset A. of arcs from V V a distance function d E R 0 for the edges of G. and a distinguished vertex o V, Output A closed walk starting and ending at o which traverses each a A and. has minimal length w r t the lifted distance function D V V R 0. which assigns to each possible arc u v V V the length of a shortest. path from u to v in G More precisely we are required to determine a. tour T minimizing X, We say that an edge u v is traversed by an arc u0 v 0 if the path connecting u0. and v 0 contains u v, In this thesis we will only deal with the case that the underlying transportation. network is a tree In the following two overview sections we remark on the known. results for general graphs too,1 2 Offline Dial a Ride Problems State of the Art.
and New Results, The Darp in its general form includes the Traveling Salesman Problem as an im. portant special case and is thus NP hard Frederickson and Guan 18 show that. the Darp is NP hard even for rather restricted classes of underlying networks such. 2004 07 05 059 IN99 2239 3,1 Introduction, as trees An interesting fact is that the Darp can be solved in polynomial time if. the graph G is a path but it is NP hard on a special tree called caterpillar which is. essentially the path with n vertices 23 4 A systematic survey studying the com. plexity of many variants of Dial a Ride problems has been undertaken by de Paepe et. al 16 15 They were able to identify maximal easy and minimal hard problems. as well as a small set of problems with unknown complexity status. The standard way to deal with NP hard problems is to look for approximation. algorithms which try to find a close to optimal solution in polynomial time For. the case of Darp for general graphs a 95 approximation algorithm was presented by. Frederickson et al 19 An improved algorithm for trees proposed by Frederickson. and Guan 18 has a performance ratio of 45, However it has been observed that another algorithm proposed by Frederickson. and Guan 18 called use MST performs even better in practice In fact most of. the solutions generated by use MST were indeed optimal whereas the performance. guarantee of use MST is only 43 This suggests to do probabilistic analysis Instead. of considering the behaviour of an algorithm w r t worst case instances we are. interested in its typical behaviour on instances drawn from a certain probability. distribution, This approach was taken by Coja Oghlan et al They first showed that use MST. solves asymptotically all instances optimal if it is run on a caterpillar 13 and later. extended this result to general trees 12 We were able to improve an intermediate. result of the last mentioned analysis which is presented in detail in Chapter 4. Another common probabilistic technique in algorithm analysis is average case an. alysis As in probabilistic analysis one assumes that the considered Darp instances. occur according to a probability distribution and shows that the behaviour of a cer. tain algorithm is good on average Being good may mean expected polynomial. running time and or better solution quality than is guaranteed for the worst case. The result shown by Coja Oghlan et al is stronger The algorithm use MST has al. ways polynomial running time in fact nearly linear running time and is optimal on. almost all large instances whereas an algorithm with good performance on average. may be bad on a large part of the instances,4 2004 07 05 059 IN99 2239.
1 3 Online Dial a Ride Problems State of the Art and New Results. 1 3 Online Dial a Ride Problems State of the Art,and New Results. Bad Guys are Rare Probabilistic Analysis of an Elementary 5 6 Probabilistic Analysis of the High Load Case commissioned into one packaging unit for delivery

Related Books