Accession Number : ADA254553


Title :   Combinatorial Algorithms for Optimization Problems


Descriptive Note : Doctoral thesis


Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Cohen, Edith


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254553.pdf


Report Date : Jun 1991


Pagination or Media Count : 170


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.


Descriptors :   *OPTIMIZATION , *LINEAR PROGRAMMING , *COMBINATORIAL ANALYSIS , ALGORITHMS , NETWORKS , GRAPHS , THESES , TIME , POLYNOMIALS , FLOW , ADDITION , INEQUALITIES , NETWORK FLOWS , NUMBERS , YIELD , VARIABLES , CYCLES , STRUCTURES , COMPUTER PROGRAMMING , PARAMETERS , LINEAR SYSTEMS


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE