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?

  • $\begingroup$ Are you "rounding off" in the traditional sense (>0.5 rounds up, < 0.5 rounds down)? If yes, then what happens with (0, 5, 1) and (0, 7, 1)? $\endgroup$ Jun 4 '14 at 20:37
  • $\begingroup$ For simplicity sake, lets throw out the integers and just use decimals then. So in this case (0,7,1) would be chosen above (0,5,1). I edited the question to reflect that. $\endgroup$ Jun 4 '14 at 21:21
  • 1
    $\begingroup$ In the case of real values you can show the algorithm is optimal. See en.wikipedia.org/wiki/Optimal_substructure. $\endgroup$ Jun 4 '14 at 21:39
  • $\begingroup$ What's the question, exactly? It sounds like you already have a candidate algorithm for this problem. Have you tried your algorithm on some small examples? Have you tried proving that it is optimal (e.g., via induction)? Have you reviewed your textbook's chapter on greedy algs? We don't do "check my work" questions (where you paste your problem and your proposed answer and ask us to check whether it is correct for you), but if you have a specific question about how to approach the problem or something you are stuck on, feel free to edit the question to clarify what specifically you are asking. $\endgroup$
    – D.W.
    Jun 4 '14 at 22:46
  • 1
    $\begingroup$ "Is my algorithm optimal?" is still a yes/no question. I've changed the question to "How do I prove optimality?", which is suitable for the site. If you want feedback on your own proof attempt, I suggest, you add it as an answer (possibly with a note, stating you are unsure if it is correct) and people can give feedback through votes and comments. $\endgroup$
    – FrankW
    Jun 5 '14 at 4:52

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.

  • $\begingroup$ Exactly what I was looking for, I was thinking of using an exchange argument but contradiction seems easier, thanks! $\endgroup$ Jun 5 '14 at 20:42

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.