Preface
Organization
Algorithmic Challenges in M2M
(Invited Talk)
Contents
Robot Planning
The Multi-source Beachcombers' Problem
1 Introduction
1.1 Preliminaries and Notation
1.2 Outline and Results of the Paper
1.3 Related Work
2 t-SBP as a Partitioning Problem and its Hardness
2.1 A Deterministic Approximation Guarantee for 2-SBP
2.2 An Exact Solution for t-SBP with S-Uniform Swarms
3 A Randomized Algorithm for t-SBP
4 Conclusion and Open Problems
References
Multi-Robot Foremost Coverage of Time-Varying Graphs
1 Introduction
1.1 Related Results
1.2 Main Results
2 k-Agent Border Coverage in R
3 Two Agents on a Tree
4 Conclusion and Discussion
References
Strategies for Parallel Unaware Cleaners
1 Introduction
2 Model
3 Simple Cleaning Examples
4 Canonical Cleaning and General Observations
5 The Torus and the Grid Graph
6 Unaware Parallel Traversal of General Graphs
7 Conclusion
A Appendix
A.1 Canonical Cleaning
A.2 Canonical Algorithm First Visit
A.3 Analysis of Torus Algorithm
A.4 Proof of Lemma 3
A.5 Analysis of Algorithm 5
References
Minimum-Traveled-Distance Gathering of Oblivious Robots over Given Meeting Points
1 Introduction
2 Definitions
3 Basic Results
4 Exact Gathering
4.1 Classes S1, S2, and S3
4.2 Class S4: All Robots and Weber Points on a Line
4.3 Class S5: Rotations
4.4 Class S6: Reflections with Robots and Weber Points on the Axis
4.5 Class S7: Reflections with Robots but No Weber Points on the Axis
4.6 Class S8: Reflections with Weber Points but No Robots on the Axis
4.7 Class S9: Asymmetric
5 Conclusion
References
Algorithms and Data Structures
on Graphs
Fast Rendezvous with Advice
1 Introduction
1.1 Background
1.2 Model and Problem Description
1.3 Our Results
1.4 Related Work
2 The Advice and the Algorithm
3 The Lower Bound
4 Conclusion
References
Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard
1 Introduction
2 Notations and Definitions
3 The Dynamic Diameter Problem is Not in APX for Undirected Networks
4 The Dynamic Diameter Problem is NP-Complete Even for Statically Connected Networks
5 The Dynamic Diameter Problem is Not in APX for Statically Strongly Connected Networks
6 Conclusion and Future Works
References
Improved Spanners in Networks with Symmetric Directional Antennas
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 Preliminaries and Notation
2 5-Gadgets and their Properties
2.1 Outline
2.2 5-Gadgets
3 7-Spanner
4 Stretch Factor 5
5 Conclusions
References
Wireless Networks
Exploiting Geometry in the SINRk Model
1 Introduction
2 Maximum Capacity
2.1 An O(1)-Approximation for Constant k
2.2 All Pairs Maximum Capacity
3 Scheduling
4 A PTAS for Maximum Capacity with k=1
References
Interference Minimization in Asymmetric Sensor Networks
1 Introduction
2 Preliminaries and Notation
3 NP-completeness in Two Dimensions
4 The One-Dimensional Case
4.1 Properties of Optimal Solutions
4.2 A Quasi-Polynomial Algorithm
5 Further Structural Properties in One Dimension
5.1 Nearest Neighbor Algorithm and Lower Bound
5.2 Bends
6 Conclusion
References
Minimum Latency Aggregation Scheduling in Wireless Sensor Networks
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 Model and Problem Statement
2 Unit Interval Graphs
3 Optimal Algorithm for Regular Unit Interval Graphs
4 Optimal Convergecast for Grids and Tori
References
Author Index