Approximation Algorithms for identification, bin packing and scheduling problems

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The proposed research focuses on understanding the inherent computational complexity of various algorithmic questions which have arisen recently in connection with a variety of optimization, scheduling and resource allocation problems coming from Internet and telecommunications routing and usage applications, among others. Our main goal is to provide efficient (polynomial-time) algorithms for those problems, which have them, sharp approximation algorithms for those, which don't, and appropriate non-approximability results when this is appropriate. Problems of this type form a critical part of the foundations of theoretical computer science. In addition to increasing our understanding of the fundamental reasons as to why some problems are so much harder to solve than others, the discovery of efficient algorithms (when they exist) can contribute to more effective use of Internet network and processing resources, memory usage in parallel computation algorithms, more efficient pattern recognition methods in computational biology, and increased capacity for many kinds of communication networks, for example.