Parallel computational methods in integer linear programming.
Item
-
Title
-
Parallel computational methods in integer linear programming.
-
Identifier
-
AAI9130343
-
identifier
-
9130343
-
Creator
-
Lin, Yu.
-
Contributor
-
Adviser: Victor Pan
-
Date
-
1991
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
Our aim in this thesis is to tackle the most significant unknown questions about parallel computational methods in integer linear programming. These questions involve two important groups of problems: problems with a fixed number of variables and problems with equality constraints only (linear Diophantine equations). One asks whether these classes of problems are in NC, i.e., whether they can be solved by a log-space uniform system of polynomially many parallel processors in polylog time. In both cases, we obtain partial answers to those questions.;In the first case, we concentrate on the problems where the number of free variables is two. We show that integer linear programming with two variables is NC-equivalent to a strong form of the greatest common divisor problem: all the intermediate results of Euclidean algorithm plus the output of an interated modulo function with the remainder sequence from the Euclidean algorithm as arguments. The best previously known results are special cases of this. Furthermore, we show that the interated modulo function with general arguments is P-complete.;In the second case we obtain local results (in the sense of number theory). We show that solving linear equations over discrete valuation ring (with adequate computability conditions) is in ZNC. This has application to the linear Diophantine equation problem, as well as to other problems. In particular, we show that vector p-adic approximation and finding a p-component of a finitely generated Abelian group are in ZNC. We also show that finding a maximal independent set in a linear matroid is in NC.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
