Question: Consider a modification to the activity-selection problem in which each activity a i has, in addition to a start and finish time, a value

Consider a modification to the activity-selection problem in which each activity a_i has, in addition to a start and finish time, a value ν_i. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set A of compatible activities such that ∑_aki_∈Aν_kis maximized. Give a polynomial-time algorithm for this problem.

Step by Step Solution

★★★★★

3.26 Rating (164 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

We can no longer use the greedy algorithm to solve this problem However as we show the problem still has an optimal substructure which allows us to formulate a dynamic programming solution The analysi... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Introduction to Algorithms Questions!

Consider a modification of the rod-cutting problem in which, in addition to a price p i for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the...

Sometimes a transaction has to be undone after it has commited, because it was erroneously executed, for example because of erroneous input by a bank teller. a. Give an example to show that using the...

What is a modification problem? What are the three possible types of modification problems?

( 1 0 points ) Activity - Selection Problems Consider a modification to the activity - selection problem in which each activity ai has, in addition to a start and finish time, a value vi . The...

Consider a modification to the activity - selection problem in which each activity ai has, in addition to a start and finish time, a value i . The objective is no longer to maximize the number of...

Consider a modification to the activity - selection problem in which each activity a has, in addition to a start and finish time, a value Vi . The objective is no longer to maximize the number of...

Prepared by Gilberto Clavell Page 1 CHAPTER 3 PROJECT MANAGEMENT Chapter Abstract; The Project Manager is responsible for everything that is required to make the project a success - whether directly...

1. Algorithmic Paradigms (25 marks) (a) Consider the activity selection problem. An instance is a set of proposed activities that wish to use a resource. Each activity A S is defined by a pair...

Consider a modified version of the Activity Selection problem in which each activity has a profit , in addition to a start time and finish time . The goal is no longer to maximize the number of...

Write a paper that summarizes the main points of the current IFRS exposure drafts attached. Additionally, compare/contrast with current theory/standards. Each section must be a minimum of two pages....

Centaurus Limited (CL) is engaged in the business of manufacture and supply of leather jackets. Presently CL manufactures 30,000 jackets per month. Following information is available for the month of...

' A ray of white light strikes the adjacent side of a right-triangle prism at normal incidence. The triangle has angle 0 = 24. The index of refraction ranges from 2.10 to 2.18 for the wavelengths of...

Q 2 : Wehr Corporation produces one product. Total fixed costs are $ 6 0 0 , 0 0 0 . The unit selling price is $ 6 0 . 0 0 and the unit variable cost is $ 4 5 . 0 0 ( 2 0 points ) A ) Compute the...

=+regulated indus- tries such as airlines, railroads, and trucking, will charge excessive prices, products will be unsafe, and the rich would oppress the poor. Government curbs the power of...

For what values of d is the tree T of the previous exercise an order-d B-tree?

Suppose T is a multiway tree in which each internal node has at least five and at most eight children. For what values of a and b is T a valid (a,b) tree?

Consider an initially empty memory cache consisting of four pages. How many page misses does the FIFO algorithm incur on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)?

Problem 1.1 Not all probability distributions or their inverse are always easy to calculate, e.g. using Excel functions. In such cases, simulation can often be used. Here are a couple of such...

Hubbard's Pet Foods is financed 80 percent by common stock and 20 percent by bonds. The expected return on the common stock is 12 percent and the rate of interest on the bonds is 6 percent. Assuming...

What are the advantages of Event - Driven programming