pith. sign in

arxiv: 1907.02858 · v1 · pith:3ICFJBNMnew · submitted 2019-07-03 · 🧮 math.OC

Improved Bounds for Open Online Dial-a-Ride on the Line

Alexander Birx , Yann Disser , Kevin Schewior This is my paper

Pith reviewed 2026-05-25 10:25 UTC · model grok-4.3

classification 🧮 math.OC
keywords dial-a-rideonline algorithmscompetitive ratioreal linelower boundupper boundTSP
0
0 comments X

The pith

The competitive ratio for open online Dial-a-Ride on the line is at most 2.6662 and at least 2.0585.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tightens the competitive ratio bounds for the open non-preemptive online Dial-a-Ride problem on the real line, where a server must serve requests that appear over time. It establishes a lower bound of 2.0585 that is the first to strictly separate Dial-a-Ride from online TSP on the line and remains the best known even for general metrics. An algorithm is introduced that achieves an upper bound of 2.6662, improving on the previous 2.9377, and the analysis of this algorithm is shown to be tight. These results matter because they quantify how much extra cost the online serving of pickups and deliveries imposes compared to touring problems.

Core claim

We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

What carries the argument

Adversarial request sequences for the lower bound combined with a deterministic online algorithm whose movement decisions achieve the 2.6662 ratio in the open non-preemptive line model.

If this is right

  • Dial-a-Ride on the line is strictly harder than TSP in the online setting.
  • Any online algorithm for request serving on the line must sometimes incur at least 2.0585 times the optimal offline cost.
  • The 2.6662 ratio gives a concrete performance guarantee for a deterministic strategy that improves prior guarantees.
  • The lower bound construction applies directly to arbitrary metric spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The numerical separation may guide the search for similar gaps in other linear or interval-based online problems.
  • The tight upper-bound analysis could be adapted to obtain matching ratios in restricted subclasses of request sequences.
  • Practical dispatch systems on a line could benchmark against the 2.6662 figure as a worst-case target.

Load-bearing premise

The bounds are derived specifically for the open non-preemptive model on the real line metric.

What would settle it

An explicit request sequence on the line where the given algorithm exceeds ratio 2.6662, or a different online algorithm that stays below 2.0585 against all sequences.

Figures

Figures reproduced from arXiv: 1907.02858 by Alexander Birx, Kevin Schewior, Yann Disser.

Figure 1
Figure 1. Figure 1: Overview of our bounds for SmarterStart. The functions f1 (green) / f2 (red) are upper bounds for the cases where SmarterStart waits / does not wait before starting the final schedule, respectively. The upper bounds are drawn solid in the domains where they are tight for their corresponding case. The functions g1 and g2 (blue) are general lower bounds. References [1] Norbert Ascheuer, Sven Oliver Krumke, a… view at source ↗
read the original abstract

We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript considers the open non-preemptive online Dial-a-Ride problem on the real line. It establishes a lower bound of 2.0585 on the competitive ratio (the first strict separation from online TSP on the line and the best known even for general metrics) via an explicit construction, and presents an algorithm achieving an upper bound of 2.6662 whose analysis is stated to be tight.

Significance. If the bounds and tightness hold, the work improves the best known upper bound from 2.9377 and supplies the first separation result between Dial-a-Ride and TSP on the line under competitive analysis. The explicit lower-bound construction and the claim of tight algorithm analysis are clear strengths that would strengthen the literature on online metric optimization.

minor comments (3)
  1. [Abstract] The abstract states the numerical bounds without indicating the source of the constants (e.g., solution of a particular optimization problem or case analysis); a brief parenthetical reference to the relevant section would improve readability.
  2. Notation for the server position, request release times, and the distinction between open and closed variants should be introduced once in a dedicated preliminary section and used consistently thereafter.
  3. Figure captions should explicitly state the metric, the online algorithm, and the offline optimum being compared so that each figure is self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive review and recommendation of minor revision. The report lists no specific major comments.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a lower bound of 2.0585 via an explicit adversarial request sequence on the line and an upper bound of 2.6662 via analysis of a concrete online algorithm, both measured against the optimal offline solution OPT. These constructions and analyses are self-contained within the open non-preemptive model and do not reduce any claimed result to a fitted parameter, self-citation chain, or definitional renaming. The separation from online TSP is obtained directly from the differing request structures rather than by importing uniqueness theorems or ansatzes from prior author work. No load-bearing step equates a prediction to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities. Relies only on standard definitions of competitive ratio and the line metric.

axioms (1)
  • domain assumption Standard model of open non-preemptive online Dial-a-Ride on the real line with requests appearing over time.
    Invoked in the problem definition and bound statements.

pith-pipeline@v0.9.0 · 5634 in / 1112 out tokens · 24203 ms · 2026-05-25T10:25:07.705866+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 1 internal anchor

  1. [1]

    Onlin e dial-a- ride problems: Minimizing the completion time

    Norbert Ascheuer, Sven Oliver Krumke, and J¨ org Rambau. Onlin e dial-a- ride problems: Minimizing the completion time. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Scienc e (STACS), pages 639–650, 2000

    work page 2000

  2. [2]

    Atallah and S

    Mikhail J. Atallah and S. Rao Kosaraju. Efficient solutions to some t rans- portation problems with applications to minimizing robot arm travel. SIAM Journal on Computing , 17(5), 1988

    work page 1988

  3. [3]

    Ausiello, E

    G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo . Al- gorithms for the on-line travelling salesman. Algorithmica, 29(4):560–581, 2001

    work page 2001

  4. [4]

    Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line

    A. Birx and Y. Disser. Tight analysis of the smartstart algorithm f or online dial-a-ride on the line. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS) , 2019. Full version: https://arxiv.org/abs/1901.04272

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  5. [5]

    Tight bounds for online TSP on the line

    Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknech t, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schl¨ oter, and Leen Stougie. Tight bounds for online TSP on the line. In Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA) , pages 994–1005, 2017. 28

    work page 2017

  6. [6]

    Krumke, Willem E

    Michiel Blom, Sven O. Krumke, Willem E. de Paepe, and Leen Stougie. The online TSP against fair adversaries. INFORMS Journal on Computing , 13(2):138–148, 2001

    work page 2001

  7. [7]

    The finite capacity dial- a-ride problem

    Moses Charikar and Balaji Raghavachari. The finite capacity dial- a-ride problem. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS) , pages 458–467, 1998

    work page 1998

  8. [8]

    de Paepe, Jan Karel Lenstra, Jiri Sgall, Ren´ e A

    Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, Ren´ e A. Sitters, and Leen Stougie. Computer-aided complexity classification of dial-a-ride pro blems. INFORMS Journal on Computing , 16(2):120–132, 2004

    work page 2004

  9. [9]

    On-line single-server dial- a-ride prob- lems

    Esteban Feuerstein and Leen Stougie. On-line single-server dial- a-ride prob- lems. Theoretical Computer Science , 268(1):91–105, 2001

    work page 2001

  10. [10]

    Gilmore and Ralph E

    Paul C. Gilmore and Ralph E. Gomory. Sequencing a one state-va riable machine: A solvable case of the traveling salesman problem. Operations Research, 12(5):655–679, 1964

    work page 1964

  11. [11]

    D. J. Guan. Routing a vehicle of capacity greater than one. Discrete Applied Mathematics , 81(1-3):41–57, 1998

    work page 1998

  12. [12]

    Th e online dial-a-ride problem under reasonable load

    Dietrich Hauptmeier, Sven Oliver Krumke, and J¨ org Rambau. Th e online dial-a-ride problem under reasonable load. In Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC) , pages 125–136, 2000

    work page 2000

  13. [13]

    Patrick Jaillet and Michael R. Wagner. Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analy ses. Oper- ations Research, 56(3):745–757, 2008

    work page 2008

  14. [14]

    Sven O. Krumke. Online optimization competitive analysis and beyo nd,

    work page

  15. [15]

    Sven O. Krumke. Online optimization: Competitive analysis and bey ond, 2002

    work page 2002

  16. [16]

    Krumke, Willem E

    Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Maarten Lip mann, Alberto Marchetti-Spaccamela, and Leen Stougie. On minimizing the m ax- imum flow time in the online dial-a-ride problem. In Proceedings of the Third International Conference on Approximation and Onlin e Algorithms (WAOA), pages 258–269, 2006

    work page 2006

  17. [17]

    Krumke, Luigi Laura, Maarten Lipmann, Alberto March etti- Spaccamela, Willem de Paepe, Diana Poensgen, and Leen Stougie

    Sven O. Krumke, Luigi Laura, Maarten Lipmann, Alberto March etti- Spaccamela, Willem de Paepe, Diana Poensgen, and Leen Stougie. Non - abusiveness helps: An O(1)-competitive algorithm for minimizing the m ax- imum flow time in the online traveling salesman problem. In Proceedings of the 5th International Workshop on Approximation Algorit hms for Com- binat...

    work page 2002

  18. [18]

    de Paepe, Rene A

    Maarten Lipmann, Xiwen Lu, Willem E. de Paepe, Rene A. Sitters, a nd Leen Stougie. On-line dial-a-ride problems under a restricted inform ation model. Algorithmica, 40(4):319–329, 2004. 29

    work page 2004

  19. [19]

    On the online dial-a-ride problem with time- windows

    Fanglei Yi and Lei Tian. On the online dial-a-ride problem with time- windows. In Proceedings of the 1st International Conference on Algorit hmic Applications in Management (AAIM) , pages 85–94, 2005

    work page 2005

  20. [20]

    Online dial-a-ride problem wit h time-windows under a restricted information model

    Fanglei Yi, Yinfeng Xu, and Chunlin Xin. Online dial-a-ride problem wit h time-windows under a restricted information model. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Inf ormation and Management (AAIM) , pages 22–31, 2006. 30 A Proof of Lemma 2.3 In this section we prove Lemma 2.3. The proof is almost identical to th e p...

    work page 2006