权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures

离散优化算法和离散结构的计算效率

基本信息

批准号：
10205217
负责人：
FUJISHIGE Satoru
金额：
$ 11.2万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

The objective of this research project is to examine the underlying combinatorial structure of optimization problems that can be solved efficiently, and to give a unifying principle for designing efficient algorithms for such a class of combinatorial optimization problems. Our major results of the project are the following.1. We succeeded in resolving the long-standing open problem of devising a combinatorial (strongly) polynomial algorithm for minimizing submodular functions. This gave great impact on the field of discrete optimization. Following this result, we also developed a fully combinatorial strongly polynomial algorithm for submodular function minimization, and a combinatorial polynomial-time algorithm for bisubmodular function minimization, a generalization of submodular function minimization.2. The second cluster of results are concerned with network optimization problems. We considered a source location problem with flow requirements in undirected networks and devised a fast algorithm for solving it. Also we developed an efficient algorithm for L_∞-minimax inverse problem of the minimum cut problem by taking a parametric approach, and we obtained a characterization of the so-called polybasic polyhedra that generalize the boundary polyhedra of generalized flows.3. As the third cluster of results, we developed a polynomial-time algorithm for finding an optimal coterie in distributed systems, and we succeeded in constructing pseudopolynomial-time algorithms for enumerating partial transversals and multiple transversals of hypergraphs arising in the fields of data mining and learning theory.Besides these results, we revealed the deep underlying relationship between the submodularity and the economic equilibrium analysis by showing the equivalence of the M^?-concavity of the relevant set function and the gross substitutes condition in the matching (or equilibrium) model with indivisible commodities.

本研究项目的目的是研究可有效解决的优化问题的潜在组合结构，并给出为这类组合优化问题设计有效算法的统一原则。我们这个项目的主要成果如下：我们成功地解决了设计最小化子模函数的组合（强）多项式算法的长期开放问题。这对离散优化领域产生了很大的影响。根据这一结果，我们还开发了子模函数最小化的全组合强多项式算法和双子模函数最小化的组合多项式时间算法，这是子模函数最小化的推广。第二组结果与网络优化问题有关。考虑无向网络中具有流量要求的源定位问题，设计了一种快速求解算法。采用参数化方法，提出了求解最小割问题的L_∞-极小极大反问题的有效算法，并得到了广义流边界多面体的所谓多基多面体的一个表征。作为第三组结果，我们开发了一种多项式时间算法，用于在分布式系统中寻找最优小圈子，我们成功地构建了伪多项式时间算法，用于枚举数据挖掘和学习理论领域中出现的超图的部分截线和多截线。除了这些结果外，我们还通过展示M^？-不可分商品匹配（或均衡）模型中相关集合函数的凹性和总量替代条件。