3
$\begingroup$

I was told this question may be better suited here.

A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose the maximum size subset of non-overlapping tasks. Choosing tasks greedily by earliest finishing time gives an optimal solution, but what about heuristics: earliest starting time, shortest length, and fewest incompatibilities? Does each heuristic find a $c$-approximate solution, for some constant $c$?

How do you typically solve problems like this? How can we know whether a $c$-approximate solution is found (i.e. a subset of tasks whose size is at least 1/$c$ of the optimum)? I don't see how we can bound a heuristic, it seems like there are a lot of possibilities for the answers that it will return.

For example, in the earliest start time heuristic, we can always guarantee that it will select one task (the first one- with earliest start time), but it doesn't seem like we can guarantee anything more.

For the shortest length, it seems like we can get closer to the optimal solution, and to me it seems like we can always guarantee that if the optimal solution is $m$ tasks, shortest length will select $m-1$ tasks.

Improve this question
$\endgroup$
5
  • $\begingroup$ The way to solve these questions is to simultaneously try to prove some bound on the approximation and try to construct a really bad example. You have to be creative and patient. $\endgroup$
    – Yuval Filmus
    Nov 11, 2014 at 21:31
  • $\begingroup$ @YuvalFilmus What do you mean by a really bad example? And how do we know if the approximation is tight if we're just playing around with things? $\endgroup$
    – Caleb J
    Nov 11, 2014 at 23:02
  • $\begingroup$ A really bad example is one on which the proposed heuristic performs poorly. $\endgroup$
    – Yuval Filmus
    Nov 11, 2014 at 23:09
  • $\begingroup$ @YuvalFilmus I think I've done that for the "earliest start" one (i.e. we can only guarantee that just one task). I also think my analysis is correct for the shortest length, but I'm not sure how to show it is correct (or come up with an approximation). $\endgroup$
    – Caleb J
    Nov 11, 2014 at 23:14
  • $\begingroup$ For each heuristic, you either need to prove that the heuristic is a $c$-approximation, or to give a sequence of examples showing that it is not a $c$-approximation for any $c$ (that is, for each integer $c$ give an example in which the approximation ratio is less than $1/c$). $\endgroup$
    – Yuval Filmus
    Nov 11, 2014 at 23:17

1 Answer 1

Reset to default
3
$\begingroup$

The shortest-task-first heuristic is a 1/2-approximation algorithm.

For a tight example, image that a compatible set $\{T_i\mid 1\leq i\leq m\}$ sorted by their finish time and the other shorter tasks $Y_i$, $1\leq i\leq m/2$, such that $Y_i$ overlaps with $T_{2i-1}$ and $T_{2i}$ for each $i$. The shortest-first heuristic finds $m/2$ tasks while the optimal solution contains $m$ tasks.

To show the approximation ratio: For any compatible set $T$ sorted by their finish time, a task in the approximation solution overlaps with at most two tasks in $T$ since it cannot contain any task as a sub-interval of it. In fact, you can always obtain a 2-approximation if you select no tasks ``covering'' another task.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you have any ideas for the fewest incompatibilities one? That is the one I am struggling most with. $\endgroup$
    – Caleb J
    Nov 12, 2014 at 0:29

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.