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

CardsList
  1. Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items

    Oct 29, 2026Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis +1Combinatorial OptimizationOnline Resource Allocation

  2. Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

    Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive AnalysisLearning-Augmented Algorithms