Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures

点击翻译按钮获取中文摘要

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.