Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal answer, but what will a task selection algorithm that selects tasks based on the fewest incompatibilities produce (i.e. what is the $c$ approximation for this algorithm, such that this algorithm will always select a solution that has at least $1/c$ the number of tasks as the optimal solution does)?

Clearly, selecting tasks that have the fewest incompatibilities will not always be optimal, and I can construct a simple case where this is true. However, I'm having trouble coming up with a $c$ approximation for this algorithm. If we have a set of tasks, and we know the optimal solution will select $k$ of them, how many tasks can we guarantee the fewest incompatibilities algorithm will select?


Your Answer

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

Browse other questions tagged or ask your own question.