[3pm. 16 Feb, 2010. S9, Old CSE, 2nd floor]
Soumitra Pal
Toy problem: You have a set of jobs j1,..jn each of which has a start time and end time. Each jobs needs to be run on a machine during the specified time interval. What are the minimum number of machines one would require to complete all the jobs? Give a greedy algorithm to solve this problem.
What happens if the intervals are known one by one and you have to take decision about the job immediately? Does your greedy solution work here? It seems that it does not work (Can you work out one counter example?). The problem seems to be solved because there is an optimal online algorithm (no algorithm can be better than that). But people have spent a lot of time on the First-Fit greedy algorithm whose performance analysis is still not closed yet. The performance of an online algorithm is expressed as how worse compared to an optimal offline algorithm (this ratio is called as competitive ratio). So far it is shown that First-Fit is 8-competitive. But it is conjectured that it is 5-competitive. Refer this link for some history: http://people.math.gatech.edu/~trotter/rprob.html.
I will discuss the optimal online algorithm and the analysis of 8-competitiveness of First-Fit.
No comments:
Post a Comment