Given n jobs, where job j has size pj, and m machines, we want to assign...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Given n jobs, where job j has size pj, and m machines, we want to assign the jobs to the machines and minimize the maximum load of any machine (the sum of the p, for jobs j assigned to it). Furthermore, the jobs are "picky": there is a bipartite graph (J, M, E) with J the jobs, M the machines, and a job j can be assigned to machine m iff (j, m) € E. Denote by OPT the cost of the optimal assignment (the maximum load of a machine). (a) Show that the greedy algorithm, which considers the jobs in an arbitrary order and assignes the job to the least loaded machine (so far) that can take it, can output a solution of cost log n OPT (for some input graph, job order and and job sizes). (b) Consider the following linear program (with variables Z€R and TRE): min subject to Z Σ jEJ: (j,m) EE Pjxjm Z Σ mEM (j,m) EE Ijm 20 Ijm = 1 Vm € M Vje J V(j, m) € E Show that if r is a verter solution to the LP, then the graph (J, M, E*) is a forest, where E* CE contains exactly the edges (j, m) € E such that Ijm > 0. (c) Root each tree in the forest in some job vertex, and assign each job to one of its children (arbitrarily) in the tree, or to its parent if it is a leaf. Show that this assignment has cost at most 20PT. Given n jobs, where job j has size pj, and m machines, we want to assign the jobs to the machines and minimize the maximum load of any machine (the sum of the p, for jobs j assigned to it). Furthermore, the jobs are "picky": there is a bipartite graph (J, M, E) with J the jobs, M the machines, and a job j can be assigned to machine m iff (j, m) € E. Denote by OPT the cost of the optimal assignment (the maximum load of a machine). (a) Show that the greedy algorithm, which considers the jobs in an arbitrary order and assignes the job to the least loaded machine (so far) that can take it, can output a solution of cost log n OPT (for some input graph, job order and and job sizes). (b) Consider the following linear program (with variables Z€R and TRE): min subject to Z Σ jEJ: (j,m) EE Pjxjm Z Σ mEM (j,m) EE Ijm 20 Ijm = 1 Vm € M Vje J V(j, m) € E Show that if r is a verter solution to the LP, then the graph (J, M, E*) is a forest, where E* CE contains exactly the edges (j, m) € E such that Ijm > 0. (c) Root each tree in the forest in some job vertex, and assign each job to one of its children (arbitrarily) in the tree, or to its parent if it is a leaf. Show that this assignment has cost at most 20PT.
Expert Answer:
Answer rating: 100% (QA)
a The greedy algorithm will always assign the current job to the least loaded machine that can take ... View the full answer
Related Book For
Posted Date:
Students also viewed these algorithms questions
-
A graph is called bipartite if its vertices can be subdivided into two sets U and V such that every edge has one endpoint in U and the other endpoint in V. For example the graph in Exercise 48 is...
-
A single machine work center has five jobs assigned to it. They are labeled, in the order of their arrival in the shop, as jobs A, B, C, D and E. The work center may work on only one job at a time...
-
A bipartite graph, G = (V, E), is a graph such that V can be partitioned into two subsets V1 and V2 and no edge has both its vertices in the same subset. a. Give a linear algorithm to determine...
-
(1) Choose all of the following statements that are correct about the time evolution of a general wave function: (I) The time evolution of a general wave function is governed by the Hamiltonian...
-
In a chemical process control system, it is valuable to control the chemical composition of the product. To do so, a measurement of the composition can be obtained by using an infrared stream...
-
What was the name of Enrons Internet trading venture?
-
Consider the following cash flow profile, and assume MARR is 10 percent/year and the finance rate is 4 percent/year. a. Determine the MIRR for this project. b. Is this project economically...
-
Keep Cool Industries, Inc., manufactures fans for personal use. Department 70 is responsible for assembling the fan. Department 71 packages them for shipment. Keep Cool recently produced 10,000 fans...
-
Two years after the first round XMP GmbH receives a second offer form B-Capital. B-Capital offers to invest 12,500,000.00 at a 60,000,000.00 pre-money valuation. What is the founders' post-round...
-
There is a lottery with n coupons and n people take part in it. Each person picks exactly one coupon. Coupons are numbered consecutively from 1 to n, n being the maximum ticket number. The winner of...
-
Na, Mg and A1 are the elements of the same period of Modern Periodic Table having one, two and three valence electrons respectively. Which of these elements (i) has the largest atomic radius, (ii) is...
-
A taxpayer overstates the amount of their charitable contributions by $4,546 and saves themselves $1,000 in taxes in doing so. When the IRS reviews the return, they determine that the taxpayer had no...
-
Consider the economy of Mexico, which is closely linked to the United States through trade, financial flows, and supply chain dynamics. An economic expansion in the US has driven up demand for goods...
-
A company sells one product. The contribution margin per unit for this product is $7. The company decides that it wants to create a fancier packaging for the product, which would increase its...
-
Solve using Laplace (f) x"+x=2t x(0)=0 1 x'(0) = 5 ans: x(t)=3sint+2t
-
Digital Fingers Glovers bought 347 pairs of gloves at $27 per pair. 200 pairs were sold in the first month, at the regular price of $43 per pair. Another 57 pairs were sold in the second month at a...
-
What are your work-life goals for the next 10 and 20 years down the road? What does Managing Change mean to you in the workplace?
-
On October 1, 2014, the Dow Jones Industrial Average (DJIA) opened at 17,042 points. During that day it lost 237 points. On October 2 it lost 4 points. On October 3 it gained 209 points. Deter-mine...
-
Determine a state variable model for the circuit shown in Figure P3.22. The state variables are x1 = i, x2 = v1, and x3 = v2. The output variable is v0(t). 12 Output FIGURE P3.22 RLC circuit.
-
Plastic extrusion is a well-established method widely used in the polymer processing industry [12]. Such extruders typically consist of a large barrel divided into several temperature zones, with a...
-
Off-road vehicles experience many disturbance inputs as they traverse over rough roads. An active suspension system can be controlled by a sensor that looks "ahead" at the road conditions. An example...
-
All three 50 kg blocks are at rest. Is the tension in rope 2 greater than, less than, or equal to the tension in rope 1? 50 kg 2 50 kg 2 50 kg
-
a. Can the normal force on an object be directed horizontally? If not, why not? If so, provide an example. b. Can the normal force on an object be directed downward? If not, why not? If so, provide...
-
You are going sledding with your friends, sliding down a snowy hill. Friction can't be ignored. Riding solo on your sled, you have a certain acceleration. Would the acceleration change if you let a...
Study smarter with the SolutionInn App