Greedy Set-Cover Algorithms
- PDF / 216,557 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 104 Downloads / 232 Views
Hence,
G
Recommended Reading
1 opt 1 i+1 ( f (;) 2 opt) 1 opt 1 i+1 = (n 2 opt) 1 ; opt
f (C i+1 ) 2 opt ( f (C i ) 2 + opt) 1
where n = jVj. Note that 1 1/opt e1/o pt . Hence,
1. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008 3. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (1999) 4. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325–330 (2004) 5. Ruan, L., Wu, W.: Broadcast routing with minimum wavelength conversion in WDM optical networks. J. Comb. Optim. 9 223– 235 (2005)
f (C i ) 2 opt (n 2) ei/o pt : Choose i such that f (C i ) 2 opt + 2 > f (C i+1 ). Then opt (n 2) ei/o pt and g i 2 opt : Therefore, n2 g 2 opt + i opt 2 + ln opt(2 + ln ı) opt
Greedy Set-Cover Algorithms 1974–1979; Chvátal, Johnson, Lovász, Stein N EAL E. YOUNG Department of Computer Science, University of California at Riverside, Riverside, CA, USA Keywords and Synonyms Dominating set; Greedy algorithm; Hitting set; Set cover; Minimizing a linear function subject to a submodular constraint
where ı is the maximum degree of input graph G. Problem Definition Applications The technique introduced in previous section has many applications, including analysis of iterated 1-Steiner trees for minimum Steiner tree problem and analysis of greedy approximations for optimization problems in optical networks [4] and wireless networks [3]. Open Problems Can one show the performance ratio 1 + H(ı) for Greedy Algorithm B for the MCDS? The answer is unknown. More generally, it is unknown how to get a clean generalization of Theorem 1.
Given a collection S of sets over a universe U, a set cover C S is a subcollection of the sets whose union is U. The set-cover problem is, given S, to find a minimumcardinality set cover. In the weighted set-cover problem, for each set s 2 S a weight ws 0 is also specified, and the goal is to find a set cover C of minimum total weight P s2C w s . Weighted set cover is a special case of minimizing a linear function subject to a submodular constraint, defined as follows. Given a collection S of objects, for each object s a non-negative weight ws , and a non-decreasing submodular function f : 2S ! R, the goal is to find a subcollecP tion C S such that f (C) = f (S) minimizing s2C ws . (Taking f (C) = j [s2C sj gives weighted set cover.)
Cross References Connected Dominating Set Local Search Algorithms for kSAT Steiner Trees Acknowledgments Weili Wu is partially supported by NSF grant ACI-0305567.
Key Results The greedy algorithm for weighted set cover builds a cover by repeatedly choosing a set s that minimize the weight ws divided by number of elements in s not yet covered by chosen sets. It stops and returns the chosen sets when they form a cover:
379
3
Data Loading...
