PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation and Inapproximability of Non-Preemptive Dial-a-Ride

Jingyang Zhao, Mingyu Xiao

arXiv:2610.30021v1cs.DS

TL;DR

The paper studies approximation of non-preemptive dial-a-ride and related minimum-ratio Steiner k-Forest. It combines a deterministic HST algorithm with randomized metric embeddings, obtaining improved approximation guarantees and conditional hardness results even on unit-edge stars.

  • Problem

    The paper addresses approximating non-preemptive DaRP, where objects stay aboard from pickup through delivery, and related minimum-ratio SkF in general symmetric metrics.

    Source: §1 · p. 2, §1.2 · p. 3

  • Method

    A deterministic approximation on HSTs and randomized metric embeddings yield the minimum-ratio SkF algorithm, while the hardness reduction uses locally computable assignment distributions.

    Source: §1.2 · pp. 3–4

  • Results

    Expected O(n^1/4 log^12 n)-approximations for DaRP and SkF accompany ETH and quantitative Gap-ETH hardness even on unit-edge stars with n=(2+o(1))k.

    Source: §1.2 · p. 3, §6.4 · p. 21

  • Takeaways & Limitations

    The results improve on prior n^(0.3+ε)-approximation ratios and establish the first superconstant inapproximability bounds for non-preemptive DaRP.

    Source: §1.2 · p. 4

    The input model permits the number of requests m and vehicle capacity k to be superpolynomial in n.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner $k$-Forest (S$k$F) in general symmetric metrics on $n$ locations. We develop a randomized polynomial-time algorithm with expected approximation ratio $\mathcal{O}(n^{1/4}\log^{11}n)$ for the minimum-ratio S$k$F. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected $\mathcal{O}(n^{1/4}\log^{12}n)$-approximations for both the non-preemptive DaRP and the S$k$F. These guarantees improve on the previous $n^{0.3+\varepsilon}$-approximation ratios for the S$k$F and the non-preemptive DaRP, where $\varepsilon>0$ is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Under the Exponential Time Hypothesis (ETH), no deterministic polynomial-time algorithm achieves an $x^{1/(\log\log x)^c}$-approximation for some constant $c>0$, where $x$ denotes either the number of locations $n$ or the vehicle capacity $k$. Under the quantitative Gap-ETH, we rule out every deterministic polynomial-time $x^{o(1)}$-approximation. These bounds hold even on unit-edge stars with $n=(2+o(1))k$.

1 Introduction

The paper studies non-preemptive dial-a-ride and related Steiner k-Forest problems, improving approximation guarantees and establishing superconstant conditional hardness for the non-preemptive problem. Its results span algorithms in general metrics and lower bounds even on unit-edge stars.

1 Introduction

  • The problem has practical routing applications, and this paper studies the non-preemptive variant, where each object stays aboard from pickup through delivery.Earlier work gave an n^(0.3+ε)-approximation for SkF and thus DaRP, while the previously known non-preemptive DaRP lower bound was only constant.Source: §1 · pp. 1–2, §1.1 · pp. 2–3

1.1 Related Work

  • Prior work showed that an α-approximation for minimum-ratio SkF yields an O(α log^2 n)-approximation for non-preemptive DaRP.Gupta et al. (2010) established this reduction; the paper improves it by a factor of log n.Source: §1.1 · p. 2, §1.2 · p. 3

1.2 Our Results

  • For minimum-ratio SkF, a randomized polynomial-time algorithm achieves expected approximation ratio O(n^1/4 log^11 n), first developing a deterministic approximation on HSTs and extending it to general metrics via randomized tree embeddings.Source: §1.2 · p. 3
  • Expected O(n^1/4 log^12 n)-approximations follow for non-preemptive DaRP and SkF, with the DaRP reduction saving a factor of log n.The DaRP guarantee combines the minimum-ratio algorithm with a refined reduction; the SkF guarantee uses the Lagrangian framework of Segev and Segev (2010).Source: §1.2 · p. 3
  • ETH excludes deterministic polynomial-time x^1/(log log x)^c-approximations for non-preemptive DaRP, separately for x=n and x=k, even on unit-edge stars with n=(2+o(1))k.Quantitative Gap-ETH excludes deterministic polynomial-time x^o(1)-approximations on the same instances.Source: §1.2 · p. 4

2 Preliminaries

The preliminaries formalize non-preemptive DaRP inputs and routes, establish notation for requests and tree spans, and define SkF and its minimum-ratio variant.

2.1 The Non-Preemptive DaRP

  • A non-preemptive DaRP instance has a symmetric metric, depot, capacity-k vehicle, and unit pickup–delivery requests; each object stays aboard until delivery.The route starts and ends empty at the depot, and the goal is to minimize total travel cost; request types may have binary multiplicities, with m and k potentially superpolynomial in n.Source: §2.1 · p. 4

2.2 Notation and Basic Concepts

  • The notation treats graph cost as the sum of edge costs counted once, distinguishes walks from paths, and defines request counts, endpoint sets, and rooted spans.A rooted span connects the root and selected endpoints, counting shared edges only once; logarithms are base two unless stated otherwise.Source: §2.2 · pp. 4–5

2.3 SkF and Minimum-Ratio Selection

  • SkF minimizes forest cost while connecting at least k requests; minimum-ratio SkF minimizes tree cost per selected request, subject to selecting at most k.Only selected requests count toward the limit, even if the tree connects other requests, and the tree need not contain a depot; randomized approximation guarantees are in expectation.Source: §2.3 · p. 5

3 Minimum-Ratio SkF and Rooted Selection

The minimum-ratio SkF is reduced to rooted selection on an HST, then extended to general metrics through randomized tree embeddings. Root enumeration and budget guessing transfer a rooted-selection guarantee to the unrooted problem.

3.1 Reduction to Rooted Selection

  • The HST model assigns each parent-child edge the difference of endpoint heights, so path costs telescope to the difference between endpoint heights.In Figure 1, the highlighted path has edge costs 4+2+2=8=h(r)−h(v).Source: §3.1 · p. 5, Figure 1 · p. 6
  • A rooted-selection instance fixes a tree root and seeks a nonempty selection of at most Q requests whose rooted-span cost per request is bounded relative to a budget.The guarantee applies when an unknown comparison set of Q requests has rooted cost at most B; the selection root need not be the routing depot.Source: §3.1 · pp. 5–6
  • An α-approximation for rooted selection yields a 4α-approximation for minimum-ratio SkF on HSTs and expected O(α log n) in general metrics.The general-metric extension uses dominating HST embeddings with expected O(log n) distortion.Source: §3.1 · p. 6
  • The reduction enumerates roots, powers-of-two request limits, and doubled budgets, then returns the feasible selection with minimum unrooted ratio.At the highest vertex of an optimal span, a guessed Q and B satisfy b/2<Q≤b and B*≤B<2B*, yielding ratio at most 4αB*/b.Source: §3.1 · p. 6

4 The Algorithm for Rooted Selection

This section develops a rooted-selection algorithm that enumerates simple instances, builds block and neighborhood candidates, and recursively reduces request classes. Its instance reduction preserves at least ⌈Q*/2⌉ requests at rooted cost at most B, with an O(n^1/4 log^10 n) rooted guarantee yielding expected O(n^1/4 log^11 n) for minimum-ratio S$k$F in general metrics.

4 The Algorithm for Rooted Selection

  • The algorithm achieves a ˜O(N^1/4) approximation by comparing block, neighborhood, and recursive candidates.For each simple instance, it returns the candidate with minimum ratio.Source: §4 · pp. 6–7

4.1 Reduction to Simple Instances

  • At an O(ℓ) loss, it suffices to solve at most ℓ simple instances, and a selection with ratio α converts to a 4ℓα-approximation for the original instance.Here ℓ = c0 log n; the simple instances preserve the existence of a comparison set in at least one instance.Source: §4.1 · p. 7

4.2 Constructing Blocks, Groups, and Request Classes

  • Source and destination endpoints are partitioned into blocks of rooted cost at most ϱB, grouped by index ranges, and requests into at most ℓ² classes.Each greedy block can be constructed in polynomial time using a tree dynamic program.Source: §4.2 · p. 8

4.3 Constructing Block and Neighborhood Candidates

  • Completion candidates are computed from block spans and endpoint neighborhoods; either a block candidate has ratio at most 8ϱℓ²B/Qµ, or every source–destination block pair has fewer than Qµ/(4ℓ²) requests.Completion chooses a nonempty eligible request set minimizing rooted cost per request and can be performed in polynomial time.Source: §4.3 · p. 9

4.4 Reducing the Instance

  • For each request class, the reduction moves nearby endpoints toward the root, retains up to N′ highest-degree sources and destinations, and recurses with target Q′ = ⌈Q*µ/2⌉ when enough requests remain.Restoring a returned request’s endpoints adds at most 2δ to its rooted cost.Source: §4.4 · p. 10

4.5 Analysis of the Instance Reduction

  • If ϱ⁴(N′ + 1)² ≥ 218N³, either a block or neighborhood candidate has ratio at most 8ϱℓ²B/Qµ, or the recursive instance retains at least Q′ comparison requests with total rooted cost at most B.The analysis assumes all such candidates exceed that ratio; moving endpoints costs at most 2δ per restored request, with δ = ϱB/(2Q*µ).Source: §4.5 · pp. 10–12, §4.4 · p. 10
  • At least ⌈Q*/2⌉ requests remain after source and destination removal, with rooted cost at most B.At most Q*/4 requests are lost through each type of removal.Source: §4.5 · p. 13

4.6 Approximation Analysis

  • Algorithm 1 achieves approximation ratio 220ℓ^10 N^1/4 for rooted selection, yielding deterministic O(n^1/4 log^10 n) on HSTs and expected O(n^1/4 log^11 n) in general metrics.Source: §4.6 · p. 13
  • The analysis compares a candidate of ratio at most 8ϱℓ^2B/Qµ against recursion on a smaller instance, then bounds the resulting ratio by induction.The recursive instance has size N′ < N; the recurrence uses 8ℓ^3ρ(N′) ≤ ρ(N)/2 and 4ℓ^3ϱ < ρ(N)/2.Source: §4.6 · pp. 13–14
  • The recursive computation has O(N) nonempty calls and runs in polynomial time, with request multiplicities stored as binary counts.Source: §4.6 · p. 14

5 Algorithms for the Non-Preemptive DaRP and Steiner k-Forest

The section derives approximation algorithms for the non-preemptive DaRP and Steiner k-Forest from a minimum-ratio S$k$F algorithm. A sharper reduction gives the DaRP an expected O(n^1/4 log^12 n)-approximation in general metrics, while the S$k$F obtains the same expected ratio through a Lagrangian framework.

5.1 The Non-Preemptive DaRP

  • The DaRP reduction repeatedly selects at most k requests using minimum-ratio S$k$F, then serves each selected tree with a feasible non-preemptive route.The resulting route costs O(α log m) times optimum; the improved theorem gives this reduction for DaRP.Source: §5.1 · pp. 14–15
  • For non-preemptive DaRP, the guarantees are deterministic O(n^1/4 log^12 n)-approximation on HSTs and randomized expected O(n^1/4 log^13 n)-approximation in general metrics, where HST embedding adds expected O(log n).Source: §5.1 · p. 14
  • The DaRP analysis bounds the total cost of selected trees by 2αHm times optimum before converting them into service walks and connecting them to the depot.The connecting walk costs at most 2opt, and the resulting route costs at most (8αHm + 2)opt.Source: §5.1 · p. 15

5.2 Steiner k-Forest

  • O(n^1/4 log^11 n) on HSTs and expected O(n^1/4 log^12 n) in general metrics are the Steiner k-Forest guarantees.The Lagrangian framework turns the minimum-ratio algorithm into an O(α log n)-approximation for S$k$F.Source: §5.2 · pp. 15–16
  • For S$k$F, the Lagrangian framework requires a budgeted tree with controlled cost and cost per connected request type; the minimum-ratio algorithm supplies one.The algorithm tests every possible request limit on one representative per type and retains trees within the budget bound.Source: §5.2 · pp. 15–16

6 Inapproximability under ETH and Gap-ETH

The section reduces satisfiability to non-preemptive DaRP instances on unit-edge stars, using locally computable assignment distributions to select requests and separate YES and NO route costs. This construction yields superconstant hardness under ETH and rules out every deterministic polynomial-time x^o(1)-approximation under quantitative Gap-ETH, even when n = (2 + o(1))k.

6.1 The Source Formula and Local Assignment Probabilities

  • A deterministic polynomial-time construction produces a constant-gap, bounded-occurrence formula ϕ and a bounded-degree graph J with locally computable assignment distributions.For suitable W, the distributions can be listed with exact rational probabilities; in YES, they are restrictions of a common distribution on satisfying assignments.Source: §6.1 · p. 17

6.2 The Birthday Graph and Request Construction

  • Birthday-graph edges receive probabilities from local assignment distributions, and a threshold maximizing m0pm0 selects retained edges that become oriented requests on a unit-edge star.In YES, each request's probability is the probability that an assignment from the common satisfying-assignment distribution covers its edge.Source: §6.2 · pp. 17–18

6.3 Completeness and Soundness

  • In YES, a small set of satisfying assignments covers all retained requests, yielding a route of cost at most U = 2B*K/a*.The assignments cover every request by a union-bound argument, and the fixed leaf order ensures each pickup precedes its delivery.Source: §6.3 · p. 19
  • In NO, birthday-graph density bounds imply every selection of at most k requests has cost per request at least 2Λ/K, forcing a high route cost.The bound extends to request sets with arbitrary endpoint counts by extending or sampling endpoint sets before applying the density bound.Source: §6.3 · p. 19

6.4 Completing the Reductions

  • ETH excludes deterministic polynomial-time x^1/(log log x)^c-approximations for x = n or k, and quantitative Gap-ETH excludes every deterministic polynomial-time x^f(x)-approximation with f(x) → 0.Both bounds hold on unit-edge stars with n = (2 + o(1))k.Source: §6.4 · p. 21
  • The reduction’s gap exceeds the assumed approximation factor, so thresholding the returned route distinguishes satisfiable from unsatisfiable formulas and contradicts ETH.For quantitative Gap-ETH, choosing a sufficiently large fixed g likewise makes the gap exceed x^f(x) while keeping the reduction and algorithm within the forbidden running time.Source: §6.4 · p. 21
  • The lower bounds also extend to randomized polynomial-time approximation algorithms under the randomized versions of ETH and quantitative Gap-ETH.The reduction is deterministic, and a feasible route below the threshold occurs with probability at least 2/3 in YES and never in NO.Source: §6.4 · p. 22

7 Omitted Proofs

The omitted proofs construct bounded-degree, constant-gap encodings and locally computable assignment distributions, then bound the probability that sampled sets avoid large components.

7.1 Proof of Proposition 1

  • For each clause, the NAE gadget is colorable exactly when its terminals are not all equal, enabling the clause construction to preserve the YES/NO gap.The construction adds a triangle joined to the three terminals; an invalid initial or variable triangle also contributes monochromatic edges in the NO analysis.Source: §7.1 · pp. 22–23
  • The color-constraint construction has O(q0) edges, is 3-colorable in YES, and has at least ε0q0 monochromatic edges in NO.Expander equality edges reduce degree while preserving a constant gap and making inequality edges a matching.Source: §7.1 · p. 23
  • Four random-permutation levels yield a YES distribution independent of the starting satisfying coloring, while nine constraints per edge preserve a constant NO gap and bounded occurrence.The edge constraints comprise eight multiplication constraints and one color constraint.Source: §7.1 · p. 24
  • The Boolean encoding preserves a constant NO gap and bounded variable occurrence, while keeping the resulting formula size linear in q0.In YES, the encoded values and specified auxiliaries satisfy the formula.Source: §7.1 · pp. 24–25
  • For sets W whose J-components have at most four positions, the proof computes local distributions without knowing a satisfying coloring and verifies local clause satisfaction.A component contains at most two color variables, whose equality or inequality relation can be inferred from paths in B.Source: §7.1 · pp. 25–26

7.2 Proof of Lemma 14

  • The Lemma 14 proof bounds the probability that a random pair of ℓ-sets is good by counting connected five-position sets and applying Harris’s inequality and a Chernoff bound.A pair is good exactly when its induced subgraph contains no connected set of five positions.Source: §7.2 · pp. 26–27

Related papers

Loading 2610.30021v1…