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 G=(V,E) , a distinguished vertex s , 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 (log|D|+1) -approximation algorithm for the Spider Cover Problem.

### Spider Covers and Their Applications

#### Abstract

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 G=(V,E) , a distinguished vertex s , 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 (log|D|+1) -approximation algorithm for the Spider Cover Problem.
##### Scheda breve Scheda completa Scheda completa (DC)
2012
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11386/3883167`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• ND