One central question in theoretical computer science is how to solve problems accurately and quickly. Despite the encouraging development of various algorithmic techniques in the past, we are still at the very beginning of the understanding of these techniques. One particularly interesting paradigm is the greedy algorithm paradigm. Informally, a greedy algorithm builds a solution to a problem incrementally by making locally optimal decisions at each step. Greedy algorithms are important in algorithm design as they are natural, conceptually simple to state and usually efficient. Despite wide applications of greedy algorithms in practice, their behaviour is not well understood. However, we do know that in several specific settings, greedy algorithms can achieve good results. This thesis focuses on examining contexts in which greedy and greedy-like algorithms are successful, and extending them to more general settings. In particular, we investigate structural properties of graphs and set systems, families of special functions, and greedy approximation algorithms for several classic NP-hard problems in those contexts. A natural phenomenon we observe is a trade-off between the approximation ratio and the generality of those contexts.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/36073 |
| Date | 13 August 2013 |
| Creators | Ye, Yuli |
| Contributors | Borodin, Allan |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0018 seconds