Paper Info
Title
Approximation Algorithms For The Set Cover Formation By Oblivious Mobile Robots
Abstract
Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points.Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)(2) approximation ratio for an initial configuration with the lowest symmetricity (l >= 1).
Year
DOI
Venue
2014
10.1007/978-3-319-14472-6_16
PRINCIPLES OF DISTRIBUTED SYSTEMS, OPODIS 2014
Keywords
Field
DocType
Oblivious mobile robots, set cover formation, approximation algorithms, distributed algorithms
Set cover problem,Approximation algorithm,Software deployment,Computer science,Distributed algorithm,Fixed point,Robot,Mobile robot,Distributed computing
Conference
Volume
ISSN
Citations 
8878
0302-9743
3
PageRank 
References 
Authors
0.42
12
3
Name
Order
Citations
PageRank
Tomoko Izumi114121.33
Sayaka Kamei218621.28
Yukiko Yamauchi319623.91