Spider covers and their applications
type: Item
instance of: scholarly article
title: Spider covers and their applications
zbMATH Open document ID: 1257.90082
DOI: 10.5402/2012/347430
author: Filomena De Santis
author: Luisa Gargano
author: Alberto Negro
author: Ugo Vaccaro
author: Mikael Hammar
published in: ISRN Discrete Mathematics
publication date: 2013-02-21T00:00:00Z
review text: Summary: We introduce two new combinatorial optimization problems: the \textsc{Maximum Spider} problem and the \textsc{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 \textit{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 \textsc{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 \textit{Maximum Spider} and \textsc{Spider Cover} problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the \textit{Maximum Spider} problem and a \((\log|\mathcal D| + 1)\)-approximation algorithm for the \textsc{Spider Cover} problem.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6137697
Wikidata QID: Q58691001
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.5402/2012/347430
OpenAlex ID: W2152092782
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: Spanning spiders and light-splitting switches
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Q4471355
cites work: Special cases of traveling salesman and repairman problems with time windows
cites work: On approximating a geometric prize-collecting traveling salesman problem with time windows
cites work: Approximation algorithms for deadline-TSP and vehicle routing with time-windows
cites work: An approximation algorithm for the directed telephone multicast problem
cites work: Q5687193
cites work: A threshold of ln n for approximating set cover
cites work: Q3056948
cites work: An analysis of approximations for maximizing submodular set functions—I
description: scientific article; zbMATH DE number 6137697