patternMinor
Does a greedy task selection algorithm find a c-approximate solution?
Viewed 0 times
selectionapproximatesolutionalgorithmdoesfindgreedytask
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#32987, answer score: 3
Revisions (0)
No revisions yet.