Algorithms for Scheduling and Network Problems
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
In this thesis we develop algorithms for two basic classes of problems in combinatorial optimization deterministic machine scheduling and network optimization. In the first part of the thesis we consider approximation algorithms for two basic scheduling environments shop scheduling and parallel machine scheduling. We give approximation algorithms for shop scheduling that significantly improve upon the performance of previous algorithms. We then study on-line approximation algorithms for parallel machine scheduling. In the second part of the thesis we present several theoretical and practical results about parallel algorithms for network optimization problems.
- Theoretical Mathematics