Does a greedy task selection algorithm find a c-approximate solution?

Question

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.

• Yuval Filmus: 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.
• Caleb J: @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?
• Yuval Filmus: A really bad example is one on which the proposed heuristic performs poorly.
• Caleb J: @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).
• Yuval Filmus: 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$).

Answer 1

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.

• Caleb J: Do you have any ideas for the fewest incompatibilities one? That is the one I am struggling most with.