Current filters:

Search Results

  • <<
  • 1
  • >>
Item hits:
  • Thesis

  • Authors: Angelopoulos, Spyridon (2006)

  • Greedy-like algorithms have been a popular approach in combinatorial optimization, due to their conceptual simplicity and amenability to analysis. Surprisingly, it was only recently that a formal framework for their study emerged. In particular, Borodin, Nielsen and Rackoff introduced the class of priority algorithms as a model for abstracting the main properties of (deterministic) greedy-like algorithms; they also showed limitations on the approximation power of such algorithms for various scheduling problems. In this thesis we extend and modify the priority-algorithm framework so as to make it applicable to a wider class of optimization problems and settings. More precisely, we first derive strong lower bounds on the approximation ratio of priority algorithms for two well-studied...