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

Development of Algorithm Theory Based on Mathematical Programming and Probability Tyeory

基于数学规划和概率理论的算法理论发展

基本信息

批准号：
15500008
负责人：
FUJITO Toshihiro
金额：
$ 1.22万
依托单位：
Toyohashi University of Technology (2004)Nagoya University (2003)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2004
项目状态：
已结题

项目摘要

・After introducing a generalization of the vertex cover problem on graphs with vertex and edge constraints, we show it to be polynomially approximable within a factor of 2,using an extended version of the submodular set cover algorithm.・The tree cover problem is known approximable within a factor of 2 only when all the edge costs are uniform, whereas some related problems such as vertex cover and edge dominating set are 2-approximable under general costs. We develop a primal-dual algorithm for tree cover and show that its approximation factor is 2 when only two kinds of edge weights, differing by a multiplicative factor of at least 2,are allowed.・While several 2-approximation NC algorithms are known for the vertex cover problem on graphs, no such algorithm is known for the connected vertex cover problem. We develop 2-approximation NC and RNC algorithms for tree cover and connected vertex cover.・It is shown that the set multicover problem can be approximated within a factor of H(k)-1/6 by a modified greedy algorithm newly developed for set multicover.・We develop an efficient and purely combinatorial algorithm for the covering 0-1 integer program problem, and show its performance is in general as good as those of the rounding algorithms.・Extending a local search heuristic for the unweighted set packing problem, it is shown that the k-set packing problem with weights 1 and w such that w【greater than or equal】2 canbe approximated within a factor of k/2+ε.・We introduce a production planning problem called the capacitated supply-demand (CSD) problem, and, to analyze its structural properties, extend the submodular set cover problem to the one, called submodular integer cover (SIC), with submodular constraints on integer vectors instead of on subsets. By applying the primal-dual heuristic for SIC to CSD, it is shown that CSD can be approximated by a factor dependent on the network structure but not on any numerical value.

・在介绍了具有顶点和边约束的图上的顶点覆盖问题的推广后，我们使用子模集覆盖算法的扩展版本，证明它在 2 倍内多项式近似。・仅当所有边成本均匀时，树覆盖问题才在 2 倍内近似，而一些相关问题（例如顶点覆盖和边支配集）在一般情况下是 2 近似的成本。我们开发了一种用于树覆盖的原对偶算法，并表明，当仅允许两种不同的边权重（相差至少为 2 的乘法因子）时，其近似因子为 2。・虽然已知有几种用于图上顶点覆盖问题的 2 近似 NC 算法，但对于连通顶点覆盖问题，还没有这样的算法。我们开发了用于树覆盖和连通顶点覆盖的 2 近似 NC 和 RNC 算法。・结果表明，集合多重覆盖问题可以通过新开发的集合多重覆盖的修改贪心算法在 H(k)-1/6 的因子内逼近。・我们为覆盖 0-1 整数规划问题开发了一种高效且纯组合的算法，并表明其性能在一般性与舍入算法一样好。・扩展未加权集合打包问题的局部搜索启发式，结果表明，权重为 1 和 w 且 w【大于或等于】2 的 k 集合打包问题可以在 k/2+ε 因子内近似。・我们引入称为容量供需（CSD）问题的生产计划问题，并分析其结构特性，将子模集合覆盖问题扩展到称为子模整数覆盖（SIC）的问题，其中对整数向量而不是子集进行子模约束。通过将 SIC 的原对偶启发式应用于 CSD，结果表明 CSD 可以通过依赖于网络结构而不是任何数值的因子来近似。