Combinatorial Optimization with Applications to Resource Management in Communications Networks
Abstract
The main goal of this project is to develop fundamental algorithmic techniques that can be applied to problems that arise in the context of high speed communications networks. The emphasis is on efficient algorithms for resource management. This research project has two main components The first is development of well founded algorithmic techniques for online resource allocation where one needs to make decisions based on partial data and without knowledge of the future. The main goal is to develop techniques that lead to provable guarantees on worst case performance and ensures good performance on average. Research on these problems consists of both theoretical analysis and simulation based studies. The second component is design of efficient offline resource allocation algorithms based on multi commodity flow techniques. The difference between this work and existing efforts is that we are designing and tuning the algorithms to produce approximate solutions instead of designing algorithms to produce exact solutions in theory. The result is code that is orders of magnitude faster than existing code and which achieves a precision of better than 1.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1998
- Accession Number
- ADA389177
Entities
People
- Serge Plotkin
Organizations
- Stanford University