@article {Lam:March 2005:1382-6905:157,
	author = "Lam, Tak-Wah",
	author = "Ngan, Tusen-Wan",
	author = "To, Kar-Keung",
	title = "A Tighter Extra-Resource Analysis of Online Deadline Scheduling",
	journal = "Journal of Combinatorial Optimization",
	volume = "9",
	year = "March 2005",
	abstract = "This paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee.",
	pages = "157-165(9)",
	url = "http://www.ingentaconnect.com/content/klu/joco/2005/00000009/00000002/00006854"
	doi = "doi:10.1007/s10878-005-6854-6"
}