Showing cs.DSShow all
2 papers · 1 filter
cs.DS2015
Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture
Peruvemba Sundaram Ravi, Levent Tuncel
Coffman and Sethi proposed a heuristic algorithm, called LD, for multi-processor scheduling, to minimize makespan over flowtime-optimal schedules. LD algorithm is a natural extensi…
cs.DS2013
Worst-Case Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and Flow-Time
Peruvemba Sundaram Ravi, Levent Tuncel, Michael Huang
In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules,…