Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures

这项研究的目的是考察可有效求解的优化问题的潜在组合结构，并为设计此类组合优化问题的有效算法提供统一的原则。本项目的主要成果如下：1.我们成功地解决了一个长期悬而未决的问题，即设计一个极小子模函数的组合(强)多项式算法。这对离散优化领域产生了很大的影响。在此基础上，我们还提出了子模函数极小化的完全组合强多项式算法和双子模函数极小化的组合多项式时间算法，这是子模函数极小化的推广。第二组结果与网络优化问题有关。考虑了无向网络中有流需求的源选址问题，并设计了求解该问题的快速算法。采用参数方法，给出了求解最小割问题的L_∞-极小极大反问题的一个有效算法，得到了广义流的边界多面体的广义多基本多面体的特征。作为第三类结果，我们提出了在分布式系统中寻找最优区间的多项式时间算法，并成功地构造了伪多项式时间算法来计数数据挖掘和学习理论领域中出现的超图的部分横截和多重横截；此外，我们通过证明相关集函数的M？-凹性和商品不可分匹配(或均衡)模型中的总替代条件的等价性，揭示了子模性与经济均衡分析之间的深层联系。

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.