%T On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion time
%A Clifford Stein
%A Joel Wein
%R Technical Report PCS-TR96-295
%I Dartmouth College, Computer Science
%C Hanover, NH
%D July 1996
%U http://www.cs.dartmouth.edu/reports/TR96-295.ps.Z
%X
 We give a simple proof that, for any instance of 
 a  very general class of scheduling problems,  there 
 exists a schedule of makespan at most twice that of the
 optimal possible and of total weighted completion time
 at most twice that of the optimal possible. We then
 refine the analysis, yielding variants of this theorem
 with improved constants, and give some algorithmic consequences of 
 the technique.