cs.DSNov 16, 2026
SaveBeyond 4: Improved Competitive Traveling Repairperson
Organizations: Kent State University
Abstract
With repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to for every . We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.
Figures & tables
| Variable | Description |
| A TRP request with release time , location , and weight | |
| Depot, located at | |
| Distance between locations and | |
| Earliest possible service time of request | |
| Initial time scale: | |
| Phases , , and horizons |
Table 1: Important variables used in Sections 2 and 3 and their descriptions
Figure 1: An illustration of three possible outcomes of executing the capped route at phase- horizon : ( a ) An emergency cut stops executing at elapsed time ( b ) A scheduled cut stops executing at elapsed time (i.e., absolute time ). ( c ) No cut executes fully until elapsed time . Solid blue, dashed orange, and dotted black segments, respectively, denote the route execution, return to the depot, and waiting at the depot. marks the arrival of the server at the depot. Return durations are for each of the three cases with their respective value. Phase- horizon is the absolute time after either emergency or scheduled cut, and is after no cut. An emergency cut can happen only in the time interval , the scheduled cut can only happen at time . Additionally, in phase , there will be at most a single cut (emergency or scheduled). If no cut, then executes fully until absolute time (the elapsed time ).
More in this topic
Vehicle Routing
Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.
See all 146 papersDynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral replica counts, and pays bottleneck service cost plus replica movement. It does not know future workloads. Huang, Lou, and Xiao gave an O(sqrt(log k))-competitive randomized algorithm for this problem. We prove a deterministic O(1)-competitive algorithm. For every number of experts and every k>=1, the algorithm satisfies ALG_det <= 10 C_PB OPT + (5 C_PB + 8) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. Consequently, CR_det(k)<=10 C_PB for every k>=1, so CR_det(k)=Theta(1). The multiplicative factor does not depend on the number of experts, replica budget, horizon, or workload values. Thus randomization is not needed for the asymptotic guarantee. The proof has two layers. A finite tangent envelope, summable positive resets, and a nonexpansive balanced projection reduce reciprocal-max service costs to a deterministic exact-budget fractional path. A new deterministic rounding theorem converts every such path to integral allocations with service distortion three and movement bounded by the fractional movement plus 6k. The complete reduction, rounding theorem, causal composition, and quantified main theorem are machine-checked in Lean 4 relative to the positive-body result as the sole scientific source premise. The theorem concerns the allocation model above. It does not include network topology, shared-edge congestion, or routing decisions.
Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a non-trivial competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items(a.k.a.recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which do not require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model.
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each , we first propose a deterministic learning-augmented Balance algorithm that is -robust and -consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is -competitive against an oblivious adversary, improving over the deterministic -competitive Balance benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of for deterministic online algorithms. Moreover, we establish a lower bound of on the competitive ratio of randomized online algorithms, improving the previous lower bound of . Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is -robust and -consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.