explain how to solve the evacuation-route problem, Macroeconomics

Assignment Help:

You are the mayor of a beautiful city by the ocean, and your city is connected to the mainland by a set of k bridges. Your city manager tells you that it is necessary to come up with an evacuation plan in the event of a hurricane. Your idea is to add a sign at each intersection pointing the direction of the route to the closest of the k bridges. You realize that this can be modeled as a graph problem, where the street intersections are nodes, the roads are edges, and the edge weights give the driving time between two adjacent intersections. Note that some of the roads in your city are one-way roads.

(a) Explain how to solve the evacuation-route problem in O(mlog n) time, where n is the number of intersections and m is the number of streets connecting two adjacent intersections. Note that the number of bridges k is not a constant, that is, it may depend on n and m. Therefore, a running time of O(k · mlog n) is not an acceptable solution. (Although I will give half credit for such a solution.) The output of your algorithm will be a labeling of the intersections, with an arrow pointing to the road to take to the closest bridge.

(b) Some of the bridges can hold more capacity than others. For 1 ≤ i ≤ k, we associate a positive numeric weight ci with each bridge. To encourage people to use bridges with higher capacity, we treat distances to different bridges differently. In particular, if δ is the actual distance from some intersection to bridge i, we assign it a capacity-weighted distance of δ/ci. Therefore, the higher the bridge capacity is, the lower the weighted distance. Present an O(mlog n) time algorithm to solve the evacuation-route problem using capacity-weighted distances. (Again, I will give half credit for a solution running in O(k · mlog n) time.

Problem 4 additional info: 2b - some of the bridges will be higher capacity. Their weights will be function of (distance/number of lanes) → this will give us shorter weight and we can treat it as a better route to take even though the distance is farther away.

 


Related Discussions:- explain how to solve the evacuation-route problem

How big is buffer-caesar saladis, 1.  You are managing a breakfast and lunc...

1.  You are managing a breakfast and lunch only restaurant that sells all-inclusive plated meals (i.e. all lunches include any protein or hot foods as well as salads and sides on a

Statics and dynamics, Statics and Dynamics   Economic models deal with s...

Statics and Dynamics   Economic models deal with stock and flow variables. These variables can be in one of the two states - equilibrium or disequilibrium - at a particular poin

Compute total demand and firms profit, Suppose three identical firms are e...

Suppose three identical firms are engaged in Cournot competition in quantities. They all have marginal costs equal to 40. Market demand is given by: P(X) = 200 - X = 200 - (x

Determine the total value of loan in an economy, The total value of loan in...

The total value of loan in an economy is Rs. 400 million and the reserve ratio is 20 per cent. An enhance of Rs. 15 million in the money which the public keeps in commercial ba

How unemployement increases by firm relocating production, How unemployemen...

How unemployement increases by firm relocating production If unemployment increases in a specific city because of a firm relocating production, it's structural unemployment tha

Determine what would be lowest bid of sfi , Snake Farm Inc. (SFI) has been ...

Snake Farm Inc. (SFI) has been offered to submit a competitive bid for building 31 and 22, 18, and 11offshore pits per year for Athletic Inc. over the next four years.  If the bid

Elasticity, Suppose price elasticity of demand for HP laptops is -2.3. If t...

Suppose price elasticity of demand for HP laptops is -2.3. If the price of an HP laptop is $1,000, what should the new price be to have an increase of 10% in quantity demanded for

How did economists get it so wrong, Read "How Did Economists Get It So Wron...

Read "How Did Economists Get It So Wrong" by Paul Krugman and second, the blog "History of Economics Playground", by Pedro Duarte, Tiago Mata, Clement Levallois, Yann Grd...etc., t

Trade, What is the difference between merchantilism and absolute theory?

What is the difference between merchantilism and absolute theory?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd