Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures

主要研究成果如下：1.本文的主要研究成果如下。利用离散凹函数并考虑可能有界的边际支付，我们建立了双边匹配市场理论中标准的Gale和Shapley的婚姻模型和Shapley和Shubik的分配模型的一般推广，并证明了该模型存在两两稳定的结果。我们给出了单调最小-最大连通划分问题的第一个多项式时间算法，并证明了当代价函数不是单调时，最小-最大连通划分问题是NP-难的，即使代价函数是单调的，最小和连通划分问题也是NP-难的。我们还考虑了动态网络中的疏散问题，作为树划分问题的一个应用。双子模函数是子模函数的自然“有向”或“带符号”扩展，具有几个应用。我们已经调查了…将通常的子模函数极小化算法的强多项式形式推广到双子模函数极小化(BSFM)的难度更大，我们给出了一种绕过这一困难的方法。这一新方法给出了BSFM的第一个组合强多项式算法。我们考虑了具有三个连通性要求(弧连通性要求和两种顶点连通性要求)的最小费用源选址问题及其推广，并证明了无向网络中具有边连通性要求的源选址问题是强NP难的。此外，我们还证明了具有三个连通性要求的源定位问题是不可逼近的，除非NP中的每个问题都有一个O(N log^2N)时间确定算法。这里D表示给定要求的总和。我们还设计了(1+in D)-近似算法来解决所有扩展的源定位问题，如果我们有完整的容量和需求函数。我们研究了在无向图的顶点集上挖掘的具有离散核的支持向量机，称为电网络核。重点借助于电网络理论和离散度量理论对其理论性质进行了数学分析。具有这种核的支持向量机允许根据阻性电网络进行物理解释；具体地说，支持向量机决策函数对应于电势。我们考虑了在(无向)图和超图中求最小横截的问题，它可以看作是源位置问题和外部网络问题的自然推广。我们发现了极小亏集的一个有趣的结构特征，并给出了极小亏集构成树形超图的充要条件。利用这个刻划，我们得到了一个多项式时间算法，它为超图中的源定位问题和图和超图中的外部网络问题提供了第一个多项式时间算法。较少

Major results of our research are the following.1. By utilizing discrete concave functions and considering possibly bounded side payments, we have established a common generalization of the marriage model due to Gale and Shapley and the assignment model due to Shapley and Shubik that are standard in the theory of two-sided matching markets, and have shown the existence of a pairwise stable outcome in our model.2. We have presented a first polynomial-time algorithm for the monotone min-max connected partitioning problem and have shown that the min-max connected partitioning problem is NP-hard if the cost function is not monotone, and that the min-sum connected partitioning problem is NP-hard even if the cost function is monotone. We also considered an evacuation problem in dynamic networks as an application of the tree partitioning problem.3. Bisubmodular functions are a natural "directed", or "signed", extension of submodular functions with several applications. We have investigated th … More e difficulty of extending the strongly polynomial version of the ordinary submodular function minimization algorithms to bisubmodular function minimization (BSFM), and we have showen a way around the difficulty. This new method gives the first combinatorial strongly polynomial algorithm for BSFM.4. We have considered minimum-cost source-location problems and their generalizations with three connectivity requirements (arc-connectivity requirements and two kinds of vertex-connectivity requirements), and have shown that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard. Moreover, we have shown that the source location problems with three connectivity requirements are inapproximable within a ratio of c In D for some constant c, unless every problem in NP has an O (N log^2 N) -time deterministic algorithm. Here D denotes the sum of given demands. We have also devised (1+ In D) -approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions.5. We have investigated support vector machine (SVM) with a discrete kernel, named electric network kernel, mined on the vertex set of an undirected graph. Emphasis is laid on mathematical analysis of its theoretical properties with the aid of electric network theory and the theory of discrete metrics. SVM with this kernel admits physical interpretations in terms of resistive eletric networks; in particular, the SVM decision function corresponds to an electric potential.6. We nave considered a problem of finding a minimum transversal that can be regarded as a natural generalization of source location problems and external network problems in (undirected) graphs and hypergraphs. We have found an interesting structural characterization of minimal deficient sets and have shown a necessary and sufficient condition for such sets to form a tree hypergraph. By using this characterization, we have obtained a polynomial-time algorithm, which provides first polynomial-time algorithms for source location problem in hypergraphs and external network problems in graphs and hypergraphs. Less