About: Suppose that two robots can move at unit speed on a line and must visit certain points called stations infinitely often. Every station allows some maximal waiting time between two visits. The problem is to construct an optimal schedule for the robots. While the one-robot problem is easy to solve in linear time, already for two robots the complexity is open. Chuangpishit, Czyzowicz, Gasieniec, Georgiou, Jurdzinski, and Kranakis (SOFSEM 2018) found a [Formula: see text]-approximation algorithm. Here we provide a PTAS, accomplished by rounding and (perhaps more surprisingly) by using the well-quasi ordering of vectors of positive integers. The result is not very practical in the present form, but further investigation of the integer version may make it more usable.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • Suppose that two robots can move at unit speed on a line and must visit certain points called stations infinitely often. Every station allows some maximal waiting time between two visits. The problem is to construct an optimal schedule for the robots. While the one-robot problem is easy to solve in linear time, already for two robots the complexity is open. Chuangpishit, Czyzowicz, Gasieniec, Georgiou, Jurdzinski, and Kranakis (SOFSEM 2018) found a [Formula: see text]-approximation algorithm. Here we provide a PTAS, accomplished by rounding and (perhaps more surprisingly) by using the well-quasi ordering of vectors of positive integers. The result is not very practical in the present form, but further investigation of the integer version may make it more usable.
Subject
  • Robots
  • Integers
  • Computational complexity theory
  • Group theory
  • Cardinal numbers
  • Elementary mathematics
  • Approximation algorithms
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software