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

Development ofAlgorithm Theory for Dealing with Computational Uncertainty and its Engineering Applications

计算不确定性处理算法理论发展及其工程应用

基本信息

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

项目摘要

The set cover problem is that of =puling a minimum weight subfamily F, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F. The k-set cover problem is a variant in which every subset is of size at most k It has been long known that the problem can be approximated within a factor of H(k) =1+1/2+・・・+1/k by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. This research has shown, via LP duality, that an improved approximation bound of H(3) -1/6 can be attained, when the greedy heuristic is suitably modified for the case when any two distinct subset costs differ by a multiplicative factor of at least 2. Akey to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.The set multicover (MC) problem is a natural extension of the set cover problem s.t. each element requires to be covered a prescribed number of times (instead of just once as i … More n set cover). The k-set multicover (k-MV) problem is a variant in which every subset is of size at meet k The best approximation algorithm known so far is the classical greedy heuristic, whose performance ratio is H(k). It is no hard, however, to come up with a natural modification of the greedy algorithm such that the resulting performance is never worse, but could also be strictly better This research has verified that this is indeed the case by showing that such a modification leads to an improved performance ratio of H(k) -1/6 fork-MC.The tree cover(TC) problem is to compute a minimum weight connected edge set, given a connected and edge-weighted graph G, such that its vertex set forms a vertex cover for G. Unlike related problems of vertex cover or edge dominating set, weighted TC is not yet known to be approximable in polynomial time as good as the unweighted version is. Moreover, the best approximation algorithm known so far for weighted TC is far from practical in its efficiency.1. This research has shown that a factor 2 approximation can be attained efficiently (in the complexity of max flow) by a primal-dual method in the case when only two edge weights differing by at least a factor of 2 are available. Even under the limited weights as such, the primal-dual arguments used can be seen quite involved, having a nontrivial style of dual assignments as an essential part in it, unlike the case of uniform weights.2. This research has next shown that a factor 2 approximation can be attained for the minimum cost tree cover problem, i.e., with general weights, by a fast, purely combinatorial approximation algorithm. By interlacing the primal-dual schema and the local ratio technique, it determines which leaves to trim within a minimum spanning tree Less

集合覆盖问题是给定一个基集合U的加权子集族F，求出一个最小权子集族F，使得U的每个元素都被F中的某个子集覆盖。k-集合覆盖问题是一个变体，其中每个子集的大小最多为k。长期以来，人们一直知道该问题可以通过贪婪启发式在因子H（k）=1+1/2+···+1/k内近似，但除了未加权子集的情况外，没有更好的界。该研究表明，通过LP对偶，当贪婪启发式被适当地修改为任何两个不同的子集成本相差至少为2的乘法因子时，可以获得H（3）-1/6的改进的近似界。我们算法设计和分析的关键是最大匹配的Gallai-Edmonds结构定理。集合多重覆盖（MC）问题是集合覆盖问题的自然扩展。每个元素都需要覆盖规定的次数（而不是像我一样只覆盖一次） ...更多信息 n设置覆盖）。k-集多重覆盖（k-MV）问题是一个变形问题，其中每个子集的大小满足k。目前已知的最好的近似算法是经典的贪婪启发式算法，其性能比为H（k）。然而，提出贪婪算法的自然修改并不困难，使得所得到的性能永远不会更差，但也可以严格地更好。研究已经通过显示这样的修改导致H（k）-1/6 fork-MC的性能比的改进来验证确实是这种情况。树覆盖（TC）问题是计算最小权重连通边集，给定一个连通边权图G，使得它的顶点集构成G的一个顶点覆盖。与顶点覆盖或边控制集的相关问题不同，加权TC在多项式时间内的近似性还不如未加权的版本。此外，迄今为止已知的加权TC的最佳近似算法在其效率上远不实用。这项研究表明，在只有两个边的权重相差至少2倍的情况下，可以通过原始-对偶方法有效地获得2倍近似（在最大流的复杂性中）。即使在有限的权重下，所使用的原始-对偶参数也可以被认为是相当复杂的，具有非平凡风格的对偶赋值作为其中的重要部分，这与均匀权重的情况不同。该研究接下来表明，对于最小成本树覆盖问题，可以获得因子2近似，即，一般的权重，由一个快速的，纯粹的组合近似算法。通过交错原始对偶模式和局部比率技术，它确定在最小生成树内修剪哪些叶子