It is proved that every deterministic search path has competitive ratio at least $C_{\log}\approx 12.5937096701246675$ and Arb ball arithmetic provides a rigorous numerical enclosure of the constant.
Abstract
A unit-speed searcher starts at the origin of the Euclidean plane and must hit an unknown straight line whose direction and distance from the origin are both unknown. We prove that every deterministic search path has competitive ratio at least $C_{\log}\approx 12.5937096701246675$. The bound is unconditional: the path need not be cyclic, self-similar, spiral-like, or monotone in angle. For each projection direction, we compare the path with a zigzag obtained by sorting its alternating record turns. The resulting completion constraints are interpreted as jobs with scale-dependent deadlines and lower-bounded through a finite-window scheduling argument in logarithmic time. Averaging these directional bounds then uses the exact Euclidean velocity budget. In one dimension, the same method recovers the optimal cow-path constant $9$. Finally, Arb ball arithmetic provides a rigorous numerical enclosure of the constant.
A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and...
A self-similar reduction theorem is established for homogeneous search problems whose historical information is a record profile updated by pointwise maximum and the optimal deterministic planar Shoreline value $C_2^*$ is a computable real.
We consider online packing of axis-parallel squares into a unit-width strip under the Tetris and gravity constraints: An incoming square must be lowered from above along a monotonic downwards path until it reaches support from below. Fekete, Kamphans, and Schweer [Algorithmica, 2014] gave an algorithm with asymptotic c...
PAWC is proposed: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality.
We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic factor for the squared distance to the minimizer. To this end, we construct candidate worst-case trajectories by combining planar spirals with a...
Sebastian Pokutta, Bartolomeo Stellato· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.