Research is being conducted in five areas: submodular function minimization, optimal subgraphs, "meta-algorithms," scheduling theory, computational geometry, and parallel computation. It is known that, in principle, the submodular function minimization problem can be solved by a polynomial-bounded algorithm based on the ellipsoid method of linear programming. The objective of this research is to produce a computationally practical algorithm that could, for example, be utilized as a subroutine in polymatroidal network flow computations. The proposed research on "meta-algorithms" is an outgrowth of previous work on linear-time algorithms for solving optimal subgraph problems. The input to a meta-algorithm will be a problem description and the output an algorithm for solving the given problem. The work on scheduling theory is a continuation of the PI's previous research. Work is in progress on a number of open problems, such as the three-processor problem and the single-processor total tardiness problem. The research in progress in computational geometry concerns the rectilinear Steiner problem and problems concerning covering of rectilinear polygons with rectangles. These problems were suggested by issues in VLSI design. The work in parallel and distributed computation concerns methods for solving very large NP-hard problems. It is proposed to continue work on methods for randomized subproblem assignment and load balancing in a multiprocessor system. The research concerns theoretical problems that are motivated by the need for computationally practical solutions for problems from a variety of sources. Results that impact computing practice are expected.
