cs.DSNov 16, 2026

Beyond 4: Improved Competitive Traveling Repairperson

Authors: Bibek Maharjan, Gokarna Sharma

Organizations: Kent State University

Abstract

With k≥1k\geq 1 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 3+ε3+ε for every ε>0ε>0. 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

Explore similar work

Aug 15, 2026

A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

Dynamic 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.
Oct 29, 2026

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.
Jul 30, 2026

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 λ∈(0,1]λ\in (0,1], we first propose a deterministic learning-augmented Balance algorithm that is (4/λ+1/λ2)(4/λ+1/λ^2)-robust and (4+λ)(4+λ)-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is (e+1)(e+1)-competitive against an oblivious adversary, improving over the deterministic 55-competitive Balance benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of 44 for deterministic online algorithms. Moreover, we establish a lower bound of ee on the competitive ratio of randomized online algorithms, improving the previous lower bound of e/(e−1)e/(e-1). Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is (e/λ+1/λ2)(e/λ+1/λ^2)-robust and (e+λ)(e+λ)-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.