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

我们的主要研究成果如下：利用离散凹函数，考虑可能有界的侧支付，我们建立了双边匹配市场理论中标准的Gale和Shapley的婚姻模型和Shapley和Shubik的分配模型的共同推广，并证明了我们的模型中存在两两稳定的结果。我们提出了单调最小最大连通分区问题的第一个多项式时间算法，并证明了最小最大连通分区问题是np困难的，如果代价函数不是单调的，最小和连通分区问题是np困难的，即使代价函数是单调的。我们还考虑了动态网络中的疏散问题，作为树划分问题的一个应用。双模函数是子模函数的自然“有向”或“有符号”扩展，具有多种应用。我们研究了将普通次模函数最小化算法的强多项式版本扩展到双次模函数最小化（BSFM）的困难，并给出了一种绕过该困难的方法。该方法给出了BSFM.4的第一个组合强多项式算法。我们考虑了具有三种连接要求（弧线连接要求和两种顶点连接要求）的最小成本源定位问题及其推广，并表明无向网络中具有边缘连接要求的源定位问题是强np困难的。此外，我们已经证明，对于某些常数c，具有三个连通性要求的源定位问题在c In D的比率内是不可逼近的，除非NP中的每个问题都具有O （N log^2 N）时间确定性算法。这里D表示给定需求的总和。对于具有积分容量和需求函数的扩展源定位问题，我们还设计了（1+ In D）近似算法。研究了在无向图的顶点集上挖掘具有离散核（称为电网络核）的支持向量机（SVM）。重点利用电网络理论和离散度量理论对其理论性质进行了数学分析。具有此核的支持向量机允许在电阻网络方面进行物理解释；其中，SVM决策函数对应于一个电势。我们考虑了一个寻找最小截线的问题，它可以被视为（无向）图和超图中源定位问题和外部网络问题的自然推广。我们发现了最小亏集的一个有趣的结构特征，并给出了这些亏集形成树超图的充分必要条件。利用这一表征，我们得到了一个多项式时间算法，为超图中的源定位问题以及图和超图中的外部网络问题提供了第一个多项式时间算法。少

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