Description

General Description. Assume you need to go on a street trip over the US. You begin from New York City and might want to drive to San Francisco.You have :roadmapgas station areas and their gas costs Want to:minimize travel cost. Data and Constraints . Information:map of the street: G=(V, E)length of the streets: d: E? R gas costs: c: V? R Constraint: tank limit: UGoal:find a min. cos

Transcripts

The Gas Station Problem Samir Khuller Azarakhsh Malekian Julian Mestre UNIVERSITY OF MARYLAND

General Description Suppose you need to go on a street trip over the US. You begin from New York City and might want to drive to San Francisco. You have : guide service station areas and their gas costs Want to: minimize travel cost

Information and Constraints Information: guide of the street: G=(V, E) length of the streets: d: E R + gas costs: c : V R + Constraint: tank limit: U Goal: discover a min. taken a toll answer for go from s to t v 3 v 2 v 1 d(v 2 ,v 3 ) d(v 1 ,v 2 ) Capacity U d(s,v 1 ) d(v 3 ,t) c(v 2 ) c(v 3 ) c(v 1 ) v 4 s t v 5 c(v 4 ) v 6 (NYC) (SF) c(v 5 ) c(v 6 )

Finding gas costs online

Structure of the Optimal Solution Two vertices s & t A settled way Optimal arrangement includes stops at each station! In this manner we allow at most stops. v 1 v n v 2 v 3 t s 1.00$ 2.99$ 2.98$ 2.97$

The Problem we need to understand Input: Road map G=(V,E) , source s , goal t U : tank limit d : E R + c : VR + : No. of stops permitted : The underlying measure of gas at s Goal: Minimize the expense to go from s to t . Yield: The picked way The stops The measure of gas filled at every stop Gas expense is "per mile" and U is the scope of the auto in miles. We can accept we begin with 0 gas at s. c(s\')= 0 s t s\' U -

Dynamic Programming Assuming all qualities are necessary, we can locate an ideal arrangement in O(n 2 ∆ U 2 ) time. Not firmly polynomial time. The issue could be feebly NP-hard! Least cost to go from x to t in q quits, beginning with g units of gas. Pick [ x , q , g ] =

2 6 2 Start with 7 Tank capacity= 7 3 4 7 3 7 s t Why not Shortest Path? Most brief way is of length 15. Fetched = 37 = 4 7 + 3 3 Cheapest way is of length 16. Fetched = 28 = 4 2 + 2 7 + 2 3 7 3 2 7 2

One more attempt at Shortest Path Let the length of (u,v) be d(u,v) c(u), if d(u,v) U Shortest way has length 20. Taken a toll = 20 = 2 10. Least expensive way has length 30 . Taken a toll = 5 = 5 1 . 1 0 30 5 6 s t 5 Start with 10 Tank capacity= 10 0 20 2 10

Key Property Suppose the ideal arrangement of stops is u 1 ,u 2 ,… ,u . In the event that c(u i ) < c(u i+1 ) Fill up the entire tank If c(u i ) > c(u i+1 ) Just fill enough to achieve u i+1 . u i+1 u i c(u i ) c(u i+1 )

0 i f c(x) < c(y) U - d(y,x) if c(x) c(y) Solution Suppose the stop before x was y. The measure of gas we achieve x with is For every x we have to monitor at most n distinctive estimations of g. Least cost to go from x to t in q quits, beginning with g units of gas. Select [ x , q , g ] = At most q stops achieve x with g units of gas y x t d( y, x) 0 U - d(y,x)

achieve x with g units of gas t x v d(x,v) Dynamic Program OPT [v,q-1,0] + (d(x,v)- g) c(x) if c(v) c(x) & d(x,v) > g OPT [v,q-1,U-d(x,v)] + (U-g) c(x) if c(v)>c(x) Minimum expense to go from x to t in q quits, beginning with g units of gas. Select [ x , q , g ] = min v q - 1 more stops

Problem Wrap Up The given DP table can be filled in: O( n 3 ) time by the direct and innocent arrangement O( n 2 log n) time by a more complex arrangement Faster calculation utilizing an alternate methodology for the "all-sets" form Faster calculation for the settled way with =n with running time O(n log n)

Tour Gas Station issue Would get a kick out of the chance to visit an arrangement of urban communities T . We have admittance to set of corner stores S . Accept gas costs are uniform. The issue is NP-hard even with this limitation. Surmise the scope of costs the ideal arrangement utilizes, pay additional variable in estimation proportion. Manages gas organizations.

Uniform Cost Tour Gas Station There is a set S of corner stores and a set T of urban communities. Need to visit the urban areas with min cost. Gas costs are the same.

Uniform Cost Tour Gas Station Input G = (V,E) d : E R + T, S V : set of urban communities & corner stores. U : Tank Capacity Goal: Find least expensive visit going to all vertices in T & potentially some vertices in S .

Uniform Cost Tour Gas Station Problem is APX-hard since it sums up TSP. On the off chance that every city has a service station (T S) the two issues are identical: Let c(x,y) be most limited achievable way from x to y. Triangle disparity holds in c 3 U=5 4 6 3 7 10 3 4 10 4 8

Uniform Cost Tour Gas Station The technique works just when T S c(x, y) relies on upon the last stop before x . Supposition : Each city has a corner store inside separation at most U/2. U=5 x y 4 2 1 3

A straightforward case For all edges (u,v) in the visit d(u,v) (1-)U Find the TSP on the urban areas. Begin from g(x 1 ), go to x 1 Continue along the visit until x 2 , most remote city at separation at most (1-)U Go to g(x 2 ), rehash the system from g(x 2 ) Continue until you achieve x 1 . Give g(v) a chance to be closest corner store to v g(x 2 ) x 2 x k (1-)U x 1 g(x 1 ) g(x k )

Uniform Cost Tour Gas Station In this arrangement |T(x i ,x i+1 )| ≤ (1-)U |T(x i ,x i+2 )| > (1-)U Charge expense of treks to Gas Stations to the visit: (1-)U X i+1 x i X i+2 > (1-)U |T|+ U k ( 1 + 2/(1-) ) |T| Round outings to g(x i )

Uniform Cost Tour Gas Station Obtain a bound of (1 +2/(1-)) 1.5 c(OPT). Note that when =0, then we get 1.5 c(OPT). Give c(x,y) a chance to be least expensive traversal to go from x to y, with the end goal that we begin at g(x) and end at g(y). g(x) g(y) x c(x,y) y

Main issue Lack of triangle imbalance Use Christofides strategy. Join with past way to deal with get a practical arrangement. y z x

Single Gas Station Problem Suppose the businessperson lives almost a corner store. He needs to go to an arrangement of urban communities. In every excursion we can travel a separation of U .

Single Gas Station We are given G=(V,E) We need to cover the vertices in V We have stand out corner store Dist. of the most distant city to the corner store is U/2 . Every cycle has length U u/2 Cycle length not as much as U

Naïve Solution Find the TSP on urban communities & service station Chop the visit into parts of length (1-)U Connect every portion to the root This is a 1.5/(1-) guess Given by Li et al. [1991] U/2

Improved Method Group urban communities in view of their separation to the corner store Solve the issue for every gathering independently 3 U/2 2 U/2 1 U/2 =(1- i )/(1- i+1 )

Finding Segments in Layer i Guess the Min. No. of cycles: k Run Kruskal until you have k associated segments. ( R ) Double subtrees to discover cycles Chop the cycles as required Connect the k\' CCs to GS Cost(C)< 2cost(R)+k\' i+1 U We can demonstrate that k\' (2+ 1) k # of gatherings log(1- 1 )/(1-) k\'=4 Putting everything together we get an O(log 1/(1-))

Summary of The Results

Conclusion Incorporate the calculations as a feature of an "apparatus" for way arranging. Take care of the visit service station issue with discretionary gas costs. Expel the suspicion that each city has a service station at separation U/2.

Thanks for your consideration