Research in Combinatorial Optimization

组合优化研究

• 批准号: 8704184
• 负责人: Eugene Lawler
• 金额: $ 13.5万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-01 至 1990-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8704184&HistoricalAwards=false
• 关键词: Research; Combinatorial; Optimization

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.

目前正在五个方面进行研究：子模块功能 最小化，最优子图，“元算法”，调度理论， 计算几何和并行计算。 众所周知，原则上，子模函数最小化 问题可以通过多项式有界算法来解决，该算法基于 线性规划椭球法 本研究的目的 是产生一种计算上实用的算法， 例如，可用作多面体网络流中的子程序 计算。 提出的关于"元算法"的研究是以前的研究的产物， 致力于解决最优子图问题的线性时间算法。 元算法的输入将是问题描述， 输出用于解决给定问题的算法。 调度理论的工作是PI以前的工作的延续。 research. 目前正在就一些悬而未决的问题开展工作，例如 三处理机问题和单处理机总拖期 问题. 计算几何的研究进展涉及 直线Steiner问题和覆盖问题 直线多边形和矩形。 这些问题是由 VLSI设计中的问题。 并行和分布式计算的工作涉及以下方法： 解决NP难问题。 建议继续开展工作， 随机子问题分配和负载平衡的方法 多处理机系统 该研究涉及的理论问题是由 需要计算实际解决方案的问题，从各种 的来源。 预计会影响计算实践的结果。