BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR96-295
ENTRY:: March 06, 1997
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion time
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Stein, Clifford	
AUTHOR:: Wein, Joel	
DATE:: July 1996
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR96-295.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR96-295.pdf
ABSTRACT:: 
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.
END:: ncstrl.dartmouthcs//TR96-295