捐助
发表于 2025-3-23 10:22:04
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.
过分
发表于 2025-3-23 16:40:36
http://reply.papertrans.cn/16/1532/153143/153143_12.png
forthy
发表于 2025-3-23 20:24:33
,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
发表于 2025-3-23 23:45:24
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.
无法解释
发表于 2025-3-24 03:12:05
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.
抑制
发表于 2025-3-24 07:47:02
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.
使绝缘
发表于 2025-3-24 11:06:30
http://reply.papertrans.cn/16/1532/153143/153143_17.png
elastic
发表于 2025-3-24 18:07:23
,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.
完成
发表于 2025-3-24 19:08:28
,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
发表于 2025-3-25 02:05:14
,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.