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
-
REVIEW SKILLZ Directions: Simplify. Use only positive exponents. 1) 5x-4 (6x-3) 2) 15y7 20y14 3) (4h-5)3 -3 4) (3n13. '3n13.4m-8n (mn-3)2 6.3 Graphing Rational Functions Directions: Find any holes or...
-
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 =...
-
Consider 2.5 kg of austenite containing 0.65 wt% C, cooled to below 727C (1341F). (a) What is the proeutectoid phase? (b) How many kilograms each of total ferrite and cementite form? (c) How many...
-
On January 3, 2014, Ruiz Company retires equipment, which cost $25,700. No residual value is received. Prepare journal entries to record the transaction if (a) Accumulated depreciation is also...
-
It is sometimes claimed that the full cost of a product or service reflects the break-even selling price. Explain what this means. R4
-
Homestead Jeans Co. has an annual plant capacity of 65,000 units, and current production is 45,000 units. Monthly fixed costs are $ 54,000, and variable costs are $ 29 per unit. The present selling...
-
6 pts. Find the solution of the initial value problem y y(0) = -3 and write your solution in explicit form (that is, write it as y = . .. ). You will lose points if you do not write your solution in...
-
1. Eagle Rock Oil claims their gasoline additive increases fuel economy. Fifteen identical vehicles were obtained and their mileage before treatment was recorded. Using identical conditions as much...
-
ogether a baseball and a football weigh 2.10 pounds. the baseball and a soccer ball weigh 1.25 pounds, and the football and the soccer ball weigh 2.65 pounds. How much does each of the balls weigh?...
-
It is important to understand market needs to ensure that the market mixincluding product, price, promotion, and place (distribution)meets market needs. This task is difficult in a domestic setting,...
-
what is the effect of a conductor being in an alternating magnetic field?
-
Analyzing Interest Rates The Federal Reserve has control over the nation's monetary policy. Through adjusting the required reserve ratio, buying and selling government bonds on the open market, or...
-
The table below details three possible alternatives to replace existing machinery. The life of each alternative is 5 years. Assuming the cost of capital is 10%, depreciation for tax purposes of...
-
To what extent is global poverty a harm inflicted by the global economy? Defend your position through the historical information brought out through the book "From Silk to Silicon". Provide an...
-
Start a Curriculum Time li Question 46 Your at Not yet answered Marked out of 1.00 Flag question begin t expires Sta Internal control is the system of policies and procedures that is designed to:...
-
Write out the formula for the total costs of carrying and ordering inventory, and then use the formula to derive the EOQ model. Andria Mullins, financial manager of Webster Electronics, has been...
-
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...
-
Fogel Limited commenced trading as a carpet manufacturer on 1 November 1986. The accountant decided to produce a value added statement with the financial accounts for the year ended 31 October 1988....
-
In recent years several large listed companies have purchased their own ordinary shares. \section*{You are required to summarise} (a) the accounting requirements for a public listed company when it...
-
Capital plc carried on business in four product segments, namely aircraft design, hairdressing salons, import agencies and beauty products. The directors are now considering the dividend policy and...
Study smarter with the SolutionInn App