Mathematics > Optimization and Control
Title:Optimal checkpoint placement in sequential leave-taking
Abstract:A dinner guest who is drawn back into conversation may have to repeat farewells already made. We study the timing of coat operations that, with the host's acknowledgment, preserve progress along a prescribed farewell route. Contact durations and restart probabilities can differ by guest, and the coat operation can itself reopen conversation. We show that a fixed partition of the route is optimal among history-dependent policies and give an exact linear-time algorithm for choosing its checkpoints. For homogeneous routes with reliable acknowledgment we derive the fee below which a separate coat operation is optimal after each contact short of the door. In 120 pairs of synthetic 24-contact routes, with equal guest parameters within pairs, optimized placement reduces expected departure time relative to the best fixed stride by a mean of 7.9% when high-risk contacts are dispersed and 13.9% when they are consecutive. The free terminal passage can favor leaving a longer sequence of farewells until after the last coat operation.
Submission history
From: Mira Varen[v1] Fri, 20 Nov 2026 21:12:17 UTC (172 KB)