Research in Combinatorial Optimization

研究主要集中在五个方面：次模函数最小化、最优子图、“元算法”、调度理论、计算几何和并行计算。已知，原则上，次模函数最小化问题可以用基于线性规划椭球法的多项式有界算法求解。本研究的目的是产生一种计算上实用的算法，例如，可以用作多矩阵网络流计算中的子程序。本文提出的“元算法”研究是对求解最优子图问题的线性时间算法的发展。元算法的输入将是问题描述，输出将是解决给定问题的算法。对调度理论的研究是PI先前研究的延续。一些开放问题的研究工作正在进行中，例如三处理器问题和单处理器总延迟问题。计算几何中的研究主要涉及直线斯坦纳问题和用矩形覆盖直线多边形的问题。这些问题都是由VLSI设计中的问题提出的。并行和分布式计算的工作涉及解决非常大的np困难问题的方法。建议继续研究多处理器系统中随机子问题分配和负载平衡的方法。该研究涉及理论问题，这些问题是由各种来源的问题的计算实际解决方案的需要所驱动的。期望对计算实践产生影响的结果。

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.