Titlebook: Algorithms and Data Structures; 18th International S Pat Morin,Subhash Suri Conference proceedings 2023 The Editor(s) (if applicable) and T

捐助

Online Minimum Spanning Trees with Weight Predictions,rithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.

过分

forthy

,Messekommunikation — „Touch and Go“,del, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and .(.) rounds. In this work, we present an algorithm that requires only 2 colors and .(.) rounds. The number of colors is optimal since at least two colors are required for point robots [.].

ascetic

https://doi.org/10.1007/978-3-663-04576-2ng an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural . algorithm.

无法解释

https://doi.org/10.1007/978-3-642-91701-1disc containing at least . points whose radius is at most twice that of a SKEG disc. Our algorithm runs in . expected time using . expected space if .; if ., the algorithm computes a 2-approximation solution with high probability in . worst-case time with . space.

抑制

https://doi.org/10.1007/978-3-322-88734-4ach other and of equal length. We present an exact polynomial-time algorithm to compute LSFS between curves under . and .. For geometric graphs, we show that the decision problem is NP-hard even if one of the graphs consists of one edge.

使绝缘

elastic

,Online TSP with Known Locations, lower bound for both the open and the closed variant. Then, we focus on some interesting metric spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms for the problem.

完成

,The Mutual Visibility Problem for Fat Robots,del, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and .(.) rounds. In this work, we present an algorithm that requires only 2 colors and .(.) rounds. The number of colors is optimal since at least two colors are required for point robots [.].

defuse

,Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride,ng an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural . algorithm.