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

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/2···1/k by the greedy heururu，but no better bound has been be approximated within a factor of H(K)=1/2...1/k by the greedy heurury，but no better bound has been been shown cept of the uns.This research has shown，via LP duality，that an improved approximation bound of H(3)-1/6can 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 least2.Akey to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.The set multicover(MC)problem is a natextal of the callai-Edmonds structure theorem for maximum matchings.the set multi has shown，via LP duality，that an improved approximation bound of H(3)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/6fork-MC.The tree cover(TC)problem is to compute a minimum weight connectedge，given a connected set，given a connected set，given a connected of the greedy and vercedge，howing is to compute a minimum weight connected set，given a connected set，given a connectedge of the freedy of this，the treedy of this of the hard；加权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 factor2approximation 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 of2are 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 factor2approximation 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

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