Suppose you are acting as a consultant for the Port Authority of a small Pacific Rim...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Suppose you are acting as a consultant for the Port Authority of a small Pacific Rim nation. They are currently doing a multi-billion-dollar business per year, and their revenue is constrained almost entirely by the rate at which they can unload ships that arrive in the port. Here is a basic sort of problem they face. A ship arrives with n containers of weight w₁, W2, ..., wn. Standing on the deck is a set of trucks, each of which can hold K units of weight. (You may assume that K and w, are integers.) You can stack multiple containers in each truck, subject to the weight restrictions of K. The goal is to minimize the number of trucks that are needed to carry all the containers. This problem is NP-complete. A greedy algorithm you might use for this is the following. Start with an empty truck and begin piling containers 1,2,3,... onto it until you get to a container that would overflow the weight limit. (These containers might not be sorted by weight.) Now declare this truck "loaded" and send it off. Then continue the process with a fresh truck. By considering trucks one at a time, this algorithm may not achieve the most efficient way to pack the full set of containers into an available collection of trucks. (a) [10 points] Give an example of a set of weights and a value for K where this algorithm does not use the minimum number of trucks. (b) [10 points] Prove that the number of trucks used by this algorithm is within a factor of two of the minimum possible number for any set of weights and any value of K. Suppose you are acting as a consultant for the Port Authority of a small Pacific Rim nation. They are currently doing a multi-billion-dollar business per year, and their revenue is constrained almost entirely by the rate at which they can unload ships that arrive in the port. Here is a basic sort of problem they face. A ship arrives with n containers of weight w₁, W2, ..., wn. Standing on the deck is a set of trucks, each of which can hold K units of weight. (You may assume that K and w, are integers.) You can stack multiple containers in each truck, subject to the weight restrictions of K. The goal is to minimize the number of trucks that are needed to carry all the containers. This problem is NP-complete. A greedy algorithm you might use for this is the following. Start with an empty truck and begin piling containers 1,2,3,... onto it until you get to a container that would overflow the weight limit. (These containers might not be sorted by weight.) Now declare this truck "loaded" and send it off. Then continue the process with a fresh truck. By considering trucks one at a time, this algorithm may not achieve the most efficient way to pack the full set of containers into an available collection of trucks. (a) [10 points] Give an example of a set of weights and a value for K where this algorithm does not use the minimum number of trucks. (b) [10 points] Prove that the number of trucks used by this algorithm is within a factor of two of the minimum possible number for any set of weights and any value of K.
Expert Answer:
Answer rating: 100% (QA)
a Lets consider an example where the greedy algorithm doesnt use the minimum number of trucks Suppose we have containers with weights 3 4 5 and K is 6 ... View the full answer
Related Book For
Physics
ISBN: 978-0077339685
2nd edition
Authors: Alan Giambattista, Betty Richardson, Robert Richardson
Posted Date:
Students also viewed these programming questions
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...
-
Consider the problem of minimizing (x, y) = x subject to g(x, y) = (x 1) 3 y 2 = 0. (a) Show, without using calculus, that the minimum occurs at P = (1, 0). (b) Show that the Lagrange condition P =...
-
What are the major risks of downsizing?
-
Selected accounts of Urdu Company are shown below. Instructions From an analysis of the T-accounts, reconstruct (a) The October transaction entries, (b) The adjusting journal entries that were made...
-
Entropy is a (a) State function (b) Path function (c) Both (a) and (b) (d) Neither (a) nor (b).
-
Assume that you have an after-tax cost of capital of 10 percent. Compute the net present value of each of the five projects listed in the following table. Rank the above projects from 1 (best for...
-
A rope exerts a force of magnitude 750N at an angle 35 degrees above the horizontal, on a cow at rest on a horizontal floor. The coefficient of static friction between the cow and the floor is 0.50....
-
Hook Industries is considering the replacement of one of its old drill presses. Three alternative replacement presses are under consideration. The relevant cash flows associated with each are shown...
-
TranscribedText: INFO REQUIRED Cost Actg Budget Variances Static Budget units sold 20,000 Revenues 2,000,000| Variable Costs: D Materials 800,000 D mfg labour 200,000 Var Mfg OH 300,000 Total...
-
2. Suppose XiaoMing and XiaoLan have the same income and same tastes over Ultraman cards and "other goods." The only difference between them is that XiaoLan has a coupon that allows her to buy as...
-
The integral with respect to time of a force applied to an object is a measure called impulse, and the impulse applied to an object during a time interval determines its change in momentum during the...
-
For each of the following, give an example of a Markov chain with the desired properties. You may exhibit the chain in any way that makes the example clear (eg. giving the transition matrix, giving...
-
TRANSLATE THIS PSEUDO CODE INTO JAVA. A high-level algorithm for the traceFile method is given below: Initialize stack to an empty stack of CodeBlocks. Open file using filename. while file has lines...
-
Perform the forward and backward path analysis for the following diagram. Calculate the value of the total float and free float. (a) Identify the critical path. (b) If activity E were to have a 5-day...
-
The Basketball 3 Pt Shooting dataset contains 3 point team shooting percentages for the 2009-2010 season for the mens teams in four of the large conferences in NCAA Division 1 basketball. Are there...
-
Outline some of the major problems confronting an international advertiser.
-
Find the maximum current that a fully charged D-cell can supply-if only briefly-such that its terminal voltage is at least 1.0 V. Assume an emf of 1.5 V and an internal resistance of 0.10 .
-
Geoffrey drives from his home town due east at 90.0 km/h for 80.0 min. After visiting a friend for 15.0 min, he drives in a direction 30.0 south of west at 76.0 km/h for 45.0 min to visit another...
-
A charged parallel plate capacitor has the space between the plates filled with air. The capacitor has been disconnected from the battery that charged it. Describe quantitatively what happens to the...
-
A flywheel is mounted on a vertical shaft, as shown in Fig. 2.76. The shaft has a diameter \(d\) and length \(l\) and is fixed at both ends. The flywheel has a weight of \(W\) and a radius of...
-
A TV antenna tower is braced by four cables, as shown in Fig. 2.77. Each cable is under tension and is made of steel with a cross-sectional area of \(322 \mathrm{~mm}^{2}\). The antenna tower can be...
-
A building frame is modeled by four identical steel columns, each of weight \(w\), and a rigid floor of weight \(W\), as shown in Fig. 2.79. The columns are fixed at the ground and have a bending...
Study smarter with the SolutionInn App