Two Robots Patrolling on a Line: Integer Version and Approximability

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

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

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

zbMATH Keywords

approximation schemepatrollingwell-quasi ordering

Mathematics Subject Classification ID

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

Cites Work

• The theory of well-quasi-ordering: a frequently discovered concept
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Patrolling trees with mobile robots
• Pinwheel scheduling: Achievable densities
• Pinwheel scheduling with two distinct numbers
• 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)
• Patrolling a path connecting a set of points with unbalanced frequencies of visits
• Patrolling on dynamic ring networks
• Exploring graphs with time constraints by unreliable collections of mobile robots

Cited In (4)

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

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)