Two Robots Patrolling on a Line: Integer Version and Approximability

DOI10.1007/978-3-030-48966-3_16MaRDI QIDQ5041191zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Distance-based solution of patrolling problems with individual waiting times
• Patrolling a path connecting a set of points with unbalanced frequencies of visits
• Distributed patrolling with two-speed robots (and an application to transportation)
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency
• Approximation algorithms for the twin robot scheduling problem

Cites work

• A pinwheel scheduler for three distinct numbers with a tight schedulability bound
• Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors)
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Exploring graphs with time constraints by unreliable collections of mobile robots
• Patrolling a path connecting a set of points with unbalanced frequencies of visits
• Patrolling on dynamic ring networks
• Patrolling trees with mobile robots
• Pinwheel scheduling with two distinct numbers
• Pinwheel scheduling: Achievable densities
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(5)

• Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots
• Approximation algorithms for replenishment problems with fixed turnover times
• Perpetual maintenance of machines with different urgency requirements
• Distance-based solution of patrolling problems with individual waiting times
• The Fagnano triangle patrolling problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041191)