Two Robots Patrolling on a Line: Integer Version and Approximability

DOI10.1007/978-3-030-48966-3_16OpenAlexW3032187348MaRDI QIDQ5041191

Peter Damaschke

Publication date: 13 October 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-48966-3_16

zbMATH Keywords

approximation schemepatrollingwell-quasi ordering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (3)

Perpetual maintenance of machines with different urgency requirements ⋮ Approximation algorithms for replenishment problems with fixed turnover times ⋮ Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots

Cites Work

• Pinwheel scheduling with two distinct numbers
• A pinwheel scheduler for three distinct numbers with a tight schedulability bound
• Patrolling trees with mobile robots
• Pinwheel scheduling: Achievable densities
• Patrolling on dynamic ring networks
• The theory of well-quasi-ordering: a frequently discovered concept
• Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits
• Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots

This page was built for publication: Two Robots Patrolling on a Line: Integer Version and Approximability