Abstract
We consider a generalization of the set cover problem, in which elements are covered by pairs of objects, and we are required to find a minimum cost subset of objects that induces a collection of pairs covering all elements. Formally, let U be a ground set of elements and let \({\cal S}\) be a set of objects, where each object i has a non-negative cost w i . For every \(\{ i, j \} \subseteq {\cal S}\), let \({\cal C}(i,j)\) be the collection of elements in U covered by the pair { i, j }. The set cover with pairs problem asks to find a subset \(A \subseteq {\cal S}\) such that \(\bigcup_{ \{ i, j \} \subseteq A } {\cal C}(i,j) = U\) and such that ∑ i ∈ A w i is minimized.
In addition to studying this general problem, we are also concerned with developing polynomial time approximation algorithms for interesting special cases. The problems we consider in this framework arise in the context of domination in metric spaces and separation of point sets.
Due to space limitations, most proofs are omitted from this extended abstract. We refer the reader to the full version of this paper [8], in which all missing proofs are provided.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Greedy Algorithm
- Vertex Cover
- Minimum Cardinality
- Polynomial Time Approximation Scheme
- Approximation Guarantee
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chvátal, V.: A greedy heuristic for the set covering problem. Mathematics of Operations Research 4, 233–235 (1979)
Cockayne, E.J., Goodman, S.E., Hedetniemi, S.T.: A linear algorithm for the domination number of a tree. Information Processing Letters 4, 41–44 (1975)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing 23, 864–894 (1994)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45, 634–652 (1998)
Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29, 410–421 (2001)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3–20 (1997)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)
Hassin, R., Segev, D.: The set cover with pairs problem (2005), http://www.math.tau.ac.il/~segevd/Papers/SCP-Jour.pdf
Hassin, R., Tamir, A.: Improved complexity bounds for location problems on the real line. Operations Research Letters 10, 395–402 (1991)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 32, 130–136 (1985)
Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256–278 (1974)
Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM 46, 787–832 (1999)
Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13, 383–390 (1975)
Slavík, P.: Improved performance of the greedy algorithm for partial cover. Information Processing Letters 64, 251–254 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hassin, R., Segev, D. (2005). The Set Cover with Pairs Problem. In: Sarukkai, S., Sen, S. (eds) FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2005. Lecture Notes in Computer Science, vol 3821. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11590156_13
Download citation
DOI: https://doi.org/10.1007/11590156_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30495-1
Online ISBN: 978-3-540-32419-5
eBook Packages: Computer ScienceComputer Science (R0)