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的一个加权子集的家族中ful = put up put up put fut up = ut = u的重量。除了未加权子集的情况外，已显示出来。这项研究表明，通过LP二元性，可以附加h（3）-1/6的近似结合，当贪婪的启发式易变率被适当地修改时，当任何两个不同的子集的成本与至少为2的乘法因素不同时，适当地修改了我们的算法设计和分析的综合问题，以最大程度地介绍了Gallai -Edmonds的最大范围。英石。每个元素都需要覆盖规定的次数（而不是仅仅是我…更多n集盖）。 k-stet多over（k-mv）问题是一个变体，其中每个子集的大小都在遇到k k，到目前为止已知的最佳近似算法是经典贪婪的启发式算法，其性能比为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它的顶点集构成了G的顶点盖。与顶点盖或边缘主导集的相关问题不同，加权TC尚不可在多项式时间内与未加权版本一样好。此外，到目前为止，以加权TC闻名的最佳近似算法在其效率方面远非实用。1。这项研究表明，在只有两个边缘权重差异至少为2倍的情况下，可以通过一种原始偶的方法有效地实现因子2近似值（在最大流量的复杂性中）。即使在有限的权重下，也可以看到所使用的原始二重性参数，与统一权重的情况不同。这项研究接下来表明，可以通过快速，纯粹的组合近似算法将因子2近似值（即具有一般权重的最小成本覆盖问题）附加。通过插入原始偶型架构和局部比率技术，它确定了哪个在最小跨越的树内剪裁