Combinatorial Algorithms for Optimization Problems
Abstract
Linear programming is a very general and widely used framework. In this thesis we consider several combinatorial optimization problems that can be viewed as classes of linear programming problems with special structure. It is known that polynomial time algorithms exist for the general linear programming problem. It is not known, however, whether any of them are strongly polynomial. In addition, it seems that the general problem is inherently sequential. For problems with special structure, our goals are to develop sequential and parallel algorithms that are faster than those known for general linear programming and to determine whether strongly polynomial algorithms exist. (1) We develop a technique that extends the classes of problems known to have strongly polynomial algorithms, or known to be quickly solvable in parallel. This technique is used to obtain a fast parallel algorithm and a strongly polynomial algorithm for detecting cycles in periodic graphs of fixed dimension. We mention additional applications to parametric extensions of problems where the number of parameters is fixed. (2) We introduce algorithms for solving linear systems where each inequality involves at most two variables. These algorithms improve over the sequential and parallel running times of previous algorithms. These results are combined with additional ideas to yield faster algorithms for some general network flow problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1991
- Accession Number
- ADA254553
Entities
People
- Edith Cohen
Organizations
- Stanford University