1. Randomized priority algorithms
- Author
-
Angelopoulos, Spyros and Borodin, Allan
- Subjects
- *
COMPUTER scheduling , *MATHEMATICAL optimization , *CASE studies , *APPROXIMATION theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: Borodin, Nielsen and Rackoff introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF