We introduce two new combinatorial optimization problems: the Maximum Spider Problem and the Spider Cover Problem; we study their approximability and illustrate their applications. In these problems we are given a directed graph , a distinguished vertex , and a family D of subsets of vertices. A spider centered at vertex s is a collection of arc-disjoint paths all starting at s but ending into pairwise distinct vertices. We say that a spider covers a subset of vertices X if at least one of the endpoints of the paths constituting the spider other than s belongs to X. In the Maximum Spider Problem the goal is to find a spider centered at s that covers the maximum number of elements of the family D. Conversely, the Spider Cover Problem consists of finding the minimum number of spiders centered at s that covers all subsets in D. We motivate the study of the Maximum Spider and Spider Cover Problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the Maximum Spider Problem and a -approximation algorithm for the Spider Cover Problem. 1. Introduction Given a digraph and a vertex , a spider centered at is a subgraph of consisting of arc-disjoint paths sharing the initial vertex and ending into pairwise distinct vertices. The vertex is called the center of the spider. The endpoints of the paths composing the spider —other than the center —are called the terminals of the spider. In other words, a spider is a subdivision of , where is the number of terminals. Given a spider , we say that reaches a vertex if is a terminal of ; we say that the spider covers a subset of vertices if reaches at least a vertex in . In this paper we consider the approximability of the following problems. Maximum Spider Problem (MSP) We are given a digraph , a distinguished node , and a family of subsets of vertices. The objective is to find a spider centered at such that the number of subsets covered by is maximum among all possible spiders centered at . We also consider the related minimization problem, where one wants to cover all the elements of . Spider Cover Problem (SCP) As before, we are given a digraph , a distinguished vertex , and a family of subsets of vertices. The goal is to find a minimum cardinality collection of spiders centered at such that each subset is covered by at least a spider in the collection. 1.1. Motivations The Maximum Spider and the Spider Cover Problems are far reaching generalizations and unifications of several Maximum Coverage and Set Cover Problems which, in turn, are fundamental
References
[1]
P. Klein and R. Ravi, “A nearly best-possible approximation algorithm for node-weighted Steiner trees,” Journal of Algorithms, vol. 19, no. 1, pp. 104–115, 1995.
[2]
L. Gargano, M. Hammar, P. Hell, L. Stacho, and U. Vaccaro, “Spanning spiders and light-splitting switches,” Discrete Mathematics, vol. 285, no. 1–3, pp. 83–95, 2004.
[3]
D. S. Hochbaum, “Approximating covering and packing problems: set cover, vertex cover, indipendent set, and related problems,” in Approximation Algorithms For NP-Hard Problems, pp. 94–143, PWS Publishing, Boston, Mass, USA, 1997.
[4]
C. Chekuri and A. Kumar, “Maximum coverage problem with group budget constraints and applications,” in Proceedings of 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX '04), vol. 3122 of Lecture Notes in Computer Science, pp. 72–83, 2004.
[5]
J. Fakcharoenphol, C. Harrelson, and S. Rao, “The -traveling repairmen problem,” ACM Transactions on Algorithms, vol. 3, no. 4, article 40, 2007.
[6]
J. N. Tsitsiklis, “Special cases of traveling salesman and repairman problems with time windows,” Networks, vol. 22, no. 3, pp. 263–282, 1992.
[7]
R. Bar-Yehuda, G. Even, and S. Shahar, “On approximating a geometric prize-collecting traveling salesman problem with time windows,” Journal of Algorithms, vol. 55, no. 1, pp. 76–92, 2005.
[8]
N. Bansal, A. Blum, S. Chawla, and A. Meyerson, “Approximation algorithms for deadline-TSP and vehicle routing with time-windows,” in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC '04), pp. 166–174, ACM, New York, NY, USA, 2004.
[9]
M. Elkin and G. Kortsarz, “An approximation algorithm for the directed telephone multicast problem,” Algorithmica, vol. 45, no. 4, pp. 569–583, 2006.
[10]
L. Gargano, A. Rescigno, and U. Vaccaro, “Multicasting to groups in optical networks and related combinatorial optimization problems,” in Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS ’03), p. 8, 2003.
[11]
J. Desrosiers, Y. Dumas, M. M. Solomon, and F. Soumis, “Time constrained routing and scheduling,” in Network Routing, vol. 8 of Handbooks in Operations Research and Management Science, pp. 35–139, North-Holland, Amsterdam, The Netherlands, 1995.
[12]
U. Feige, “A threshold of for approximating set cover,” Journal of the ACM, vol. 45, no. 4, pp. 634–652, 1998.
[13]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ, USA, 1993.
[14]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions. I,” Mathematical Programming, vol. 14, no. 3, pp. 265–294, 1978.
