Greedily Schedule Events based on value/hours

Question

Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts 5hrs and has a value of 10 then you will gain 10 points. If you only attend for 3 hours, you only get 3*(10/5) = 6 points. The output that the algorithm should produce is the maximum number of points that can be obtained by attending combinations of various events. Note: you are allowed to leave and come back to an event.

My Algorithm (pseudocode):

• Sort all the events $E$ by order of their $v_i/h_i$ ratio to produce a new set of events $E'$ such that $E'[1]$ has a higher value/hours ratio than $E'[2]$, $E'[3]$, etc...
• $max = 0$
• For each event $e \in E'$
  • $h =$ hours that have not yet been taken
  • $max\ += h* (e_{v_i}/e_{h_i})$

Note: I did not specify in the algorithm how to determine the hours that have been scheduled/taken already but you can assume that there is an array that flags hours that have been scheduled.

I do believe that my algorithm gives the optimal result, but how do I prove this?

Answer 1

I'm assuming that the value given to $h$ in each step is "number of hours during the running of the event, which are not yet covered". (Your wording is somewhat ambiguous.)

In the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

From the constraints given, we see that the event visited at one point in time has no influence on the profit we can make at a different moment in time. Thus, the optimal solution will be to visit the most profitable event at each point in time, i.e. during each hour. Now, we only have to show that the algorithm achieves this:

Assume that there is an hour $h$ during which the algorithm suggests to visit event $e$, while visiting $e'$ would be more profitable. Since $e'$ is more profitable, it will have been put before $e$ during the first step of the algorithm. Furthermore, since $e'$ has been scheduled for $h$, $h$ must have been available when the algorithm processed $e$ and (since the algorithm never frees an hour) also when it processed $e'$. But this means that the algorithm would have scheduled $e'$ for hour $h$, contradicting our assumption. Thus we conclude that the algorithm is correct.

Answer 2

In the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

Since your algorithm is a greedy algorithm, its correctness can be proven by showing that the underlying structure is a matroid.

In your case the base set $E$ of the matroid would be all pairs $(e, h)$ (called visits in the following), where event $e$ runs during hour $h$. The weight of $(e,h)$ will be the respective value/hours ratio.

We will interpret adding $(e, h)$ to the result set as visiting $e$ during hour $h$. Thus the family of independent sets $I$ should contain all those subsets of $E$ where no two events are scheduled for the same hour, i.e. they contain no pairs $(e,h)$ and $(e',h)$, where $e\ne e'$. (The algorithm will only create such sets as intermediate or final results during its run, and each such set can occur given an appropriate set of weights on the elements of the base set.)

Now we have to show that $(E,I)$ actually is a matroid:

1. $\emptyset$ does not contain any colliding visits, so it is in $I$.
2. If $A\in I$ and $B \subset A$, then $B$ can not contain any colliding visits, as those would also be in $A$. So $B\in I$.
3. If $A\in I$ and $|B|<|A|$, there has to be an hour $h$ so that $A$ contains a visit $(e,h)$ but $B$ does not contain a visit $(e',h)$. (Remember that $A$ may cantain at most one visit for each hour.) Thus $B\cup \{(e,h)\} \in I$.

The canonical greedy algorithm resulting from this would split each event into visits for each hour. The first step then sorts the visits and the loop considers the visits in order of profit. The algorithm from the question can be considered as doing the same, but grouping visits for the same event together for the sorting. This is ok, since we have the constraint, that the profits for each of these visits are equal. So we can conclude that the algorithm is correct.