Show that the given algorithm is a 2-approximation algorithm

Assignment Help Computer Engineering

Reference no: EM132142180

Question :

Suppose that you have a set of n files that have to be copied on 1GB USB drives. You can assume that the file sizes are known and always less than or equal to 1GB.

The objective is to use the minimum possible number of USB drives. Suppose that you use the following algorithm: if the file fits in the current USB drive, add the file to the drive, otherwise, put this USB drive aside and start a new one.

The algorithm is simple in that it does not pre-arrange the files according to their sizes and it never tries to revisit previously closed USB drives to scavenge for additional space.

a. Show an example in which the algorithm uses n/2 drives but the optimum file arrangement uses only n/4 + 1.

b. Show that the given algorithm is a 2-approximation algorithm.

Reference no: EM132142180

Questions Cloud

What is the equilibrium value of a share of jones inc today : The required return on the cash flows of Jones' dividends is 14% per year. a) What is the equilibrium value of a share of Jones Inc today?

How many sandwiches do you make : Suppose you are planning a party for 10 friends. You decide to make sandwiches to serve at the party, no more than one sandwich per person.

What is the effective yield to maturity : Use Appendix B for an approximate answer but calculate your final answer using the formula and financial calculator methods.

Find sum of firms profits in the subgame perfect equilibrium : Firm 1 must decide whether to enter an industry in which firm 2 is an incumbent. To enter this industry, firm 1 must choose to build either a plant with a small

Show that the given algorithm is a 2-approximation algorithm : Show an example in which the algorithm uses n/2 drives but the optimum file arrangement uses only n/4 + 1.

Develop preliminary prototype of proposed e-commerce website : CIS5101 Management of Business Online - Describe the website structure and the purpose of each element (include snapshots and diagrams where appropriate)

Is the firm making profits or losses : A firm is currently producing 30 units of output. At this level of output produced: Its average total cost is 110 (ATC =110) The market price per unit of output

What does that indicate and how do you fix it : Suppose you are in the process of drawing the DFDs, and you have found that one of your Level 1 DFD describing a process in level 0.

Calculate the quantity of units : A firm has demand equation Q = 10 - 2P. The firm must sell an integer quantity of product and charge the same price per unit of product for all units sold.

User Account

All Pages