PaperlayerView exact revision on arXiv

Source-linked AI summary

A Note on Approximating the Rural Postman Problem below 3/2

Hong Li

arXiv:2608.27607v1cs.DS

TL;DR

The paper addresses approximation of the rural postman problem below the classical 3/2 guarantee. It adapts maximum-entropy sampling from metric TSP and gives a randomized (3/2 − ε)-approximation, while also transferring metric-TSP approximations to RPP with an ε overhead.

  • Problem

    The paper seeks an RPP approximation ratio strictly below 3/2 and examines how metric-TSP approximation guarantees transfer to RPP.

  • Method

    The approach adapts maximum-entropy spanning-tree sampling for metric TSP, using parity correction, and also applies a reduction from RPP to metric TSP.

  • Results

    A polynomial-time randomized (3/2 − ε)-approximation exists for RPP for an absolute constant ε > 10^-36; more generally, an α-approximation for metric TSP yields an (α + ε)-approximation for RPP.

  • Takeaways & Limitations

    The maximum-entropy algorithm avoids the extremely large instance-size increase associated with transferring better-than-3/2 metric-TSP guarantees, and the guarantees extend to GRP.

  • Takeaways & Limitations

    The metric-TSP reduction is polynomial-time for fixed ε but requires an extremely large instance, making its better-than-3/2 consequence mainly theoretical; the preprocessed cost function need not be metric.

Abstract

from arXiv · show

We give an approximation algorithm for the rural postman problem with approximation ratio strictly smaller than $3/2$. We obtain this result by adapting to the rural postman problem the technique of sampling from maximum entropy distributions for the metric traveling salesman problem of Karlin, Klein, and Oveis Gharan. We also observe that, for every fixed $\varepsilon>0$, any $α$-approximation algorithm for the metric traveling salesman problem yields an $(α+\varepsilon)$-approximation algorithm for the rural postman problem; this implication is already implicit in the treatment of edges that must be traversed in the work of Lampis on the inapproximability of the traveling salesman problem.

1 Introduction

The paper adapts maximum-entropy sampling from metric TSP to obtain a randomized RPP approximation strictly below 3/2, and establishes an approximation transfer from metric TSP to RPP.

  • RPP requires a minimum-cost closed walk traversing every required edge at least once.
  • Metric TSP has a classical 3/2-approximation, while maximum-entropy sampling produced strictly better-than-3/2 metric-TSP algorithms.
  • The paper adapts maximum-entropy sampling to RPP, yielding a polynomial-time randomized (3/2 −ϵ)-approximation algorithm for some constant ϵ > 10−36.
  • The algorithm preprocesses the instance, samples a spanning tree retaining required edges, applies minimum-cost parity correction, and expands the result into a feasible RPP closed walk.
  • For every fixed ε > 0, any polynomial-time α-approximation for metric TSP implies a polynomial-time (α + ε)-approximation for RPP.
  • The transfer reduction can require an extremely large metric-TSP instance, making its better-than-3/2 consequence mainly theoretical, whereas the maximum-entropy algorithm avoids this size increase.
  • The preprocessing also supports an LP relaxation whose integrality gap equals that of metric-TSP subtour elimination and is strictly below 3/2.

2 Preliminaries

The preliminaries define graph, cost, tour, and parity notation, then introduce the TSP subtour LP, spanning-tree polytope, and Q-join polyhedron used for optimization and parity correction.

  • 2.1 Notation: For a graph G, δG(S) denotes edges crossing a vertex set, while EG(S) denotes edges with both endpoints inside it.
  • 2.1 Notation: Edge-vector notation includes x(A) for summed coordinates, χA for incidence vectors, and odd(A) for odd-degree vertices of an edge multiset.
  • 2.1 Notation: Costs of edge multisets count multiplicity, and c(x) is the coordinate-weighted sum of edge costs.
  • 2.1 Notation: OPTRPP and OPTTSP denote optimum values for rural-postman and metric-TSP instances, respectively.
  • 2.2 Relaxations: TSP-LP is the subtour-elimination relaxation for complete graphs with nonnegative metric costs and is also applied to noncomplete graphs through vector extension.
  • 2.2 Relaxations: The spanning-tree polytope characterizes convex combinations of spanning trees, so minimum-cost spanning trees can be computed and bounded using vectors in the polytope.
  • 2.2 Relaxations: A Q-join has odd-degree vertex set Q; adding it to a connected multigraph makes every vertex even, and its minimum cost is characterized by the Q-join polyhedron.

3 Preprocessing and the RPP linear program

The preprocessing converts RPP into a complete graph whose required edges form a matching, while connector costs encode shortest-path distances. An LP relaxation fixes required-edge variables to one, can be optimized in polynomial time, and lower-bounds the original optimum.

  • Preprocessed complete graph: The preprocessing replaces each required edge with a private vertex pair joined by a required edge of the original cost.All other pairs receive connector edges based on shortest-path distances after projection to the original graph.
  • Preprocessed complete graph: The preprocessed graph is complete, with edges partitioned into matching required edges and connector edges.Every preprocessed vertex is incident to exactly one required edge, but required-edge costs may exceed corresponding shortest-path distances, so the full cost function need not be metric.
  • Preprocessed complete graph: A tour visiting every preprocessed vertex once and traversing every required edge has cost exactly equal to the original RPP optimum.The correspondence works in both directions: feasible RPP walks map to tours without increasing cost, and tours expand to feasible RPP walks of the same cost.
  • RPP linear program: RPP-LP uses variables only for connector edges and fixes every required-edge coordinate to one.An optimum extreme-point solution and its extension are used in the subsequent spanning-tree construction.
  • RPP linear program: Polynomial-time optimization of RPP-LP follows from explicit degree and nonnegativity constraints plus minimum-cut separation, and its optimum L satisfies L ≤ OPTRPP.The extreme point can be obtained through lexicographic optimization over the optimal face.

4 Maximum-entropy distributions

The paper converts an extreme-point RPP-LP solution into a spanning-tree-polytope vector by splitting an endpoint and adding a zero-cost unit edge. It then samples maximum-entropy spanning trees while preserving required edges through contraction.

  • From RPP-LP to spanning trees: Splitting one endpoint of a required edge creates a zero-cost edge with coordinate one, enabling the spanning-tree-polytope reduction.The construction transfers the RPP-LP coordinates to the split graph while retaining every required edge at coordinate one.
  • From RPP-LP to spanning trees: The resulting vector is feasible for TSP-LP, restricts to the spanning-tree polytope after deleting the zero-cost edge, and has cost L.Every required edge remains present with coordinate one.
  • Maximum-entropy distributions: A maximum-entropy distribution is the unique entropy-maximizing spanning-tree distribution with prescribed edge marginals.Its analysis exploits probabilistic structure to obtain slack in parity-correction constraints.
  • Maximum-entropy distributions: Approximate sampling can be performed in randomized polynomial time while keeping total variation distance at most ρ and each edge marginal at most (1 + δ)q_e.The implementation combines approximate marginal sampling with stability of maximum-entropy distributions.
  • Sampling with required edges: Contracting all required edges preserves a one-to-one correspondence between spanning-tree distributions and their marginals, while ensuring every sampled tree contains them.Parallel edges remain distinct in the resulting loopless multigraph, and required edges are restored after sampling.

5 The algorithm and approximation analysis

The algorithm samples a spanning tree retaining all required edges, applies minimum-cost parity correction, and expands the resulting Eulerian multigraph into an RPP walk. Maximum-entropy slack yields a randomized approximation ratio strictly below 3/2, with LP-relative and deterministic variants also supported.

  • Algorithm: The algorithm samples a required-edge-preserving spanning tree, computes a minimum-cost odd(T)-join, and expands the Eulerian multigraph into a feasible RPP closed walk.The implementation then computes an Eulerian traversal of the expanded multigraph.
  • Approximation analysis: Every sampled tree yields a feasible RPP walk, and its minimum-cost Q-join is bounded above by OPTRPP /2.The tree-plus-join multigraph is connected and Eulerian, and the tour-based half-cost vector certifies the join bound.
  • Approximation analysis: The ideal maximum-entropy distribution gives expected solution cost at most (3/2 − ϵ0)OPTRPP for fixed positive parameters.This follows by combining E[c+(T)] = L, the parity-correction bound, and L ≤ OPTRPP.
  • Approximation analysis: The implementable approximate distribution preserves the strict improvement after choosing sufficiently small δ and ρ, yielding an absolute ϵ > 10^-36.The randomized algorithm and its sampling, join computation, and feasibility transformations run in polynomial time.
  • Variants: A deterministic LP-relative better-than-3/2 guarantee follows by conditional-expectation derandomization after contracting required edges.No shortcutting is needed because the RPP construction returns a feasible closed walk rather than a metric TSP tour.

6 A general reduction from RPP to metric TSP

A reduction replaces each required edge by a path, forms a metric TSP instance on shortest-path distances, and lifts TSP tours back to RPP walks. For every fixed ε > 0, an α-approximation for metric TSP transfers to an (α + ε)-approximation for RPP.

  • Constructing the metric TSP instance: Each required edge is replaced by a length-k path with evenly divided cost, producing a graph H_k whose shortest-path completion is a metric TSP instance.The distances can be computed in polynomial time.
  • Approximation transfer: The optimum tour cost of the constructed metric TSP instance is at most OPTRPP.A preprocessed optimal RPP tour expands to a same-cost tour before shortest-path metric completion.
  • Lifting tours: Any metric TSP tour can be lifted in polynomial time to an RPP closed walk with an additive repair cost caused by missing path edges.The repair adds two copies of at most one missing edge on each required-edge path, preserving connectivity and degree parity.
  • Approximation transfer: For every fixed ε > 0, running an α-approximation on the constructed instance yields an (α + ε)-approximation for RPP in polynomial time.The construction has O(k|R|) vertices, with k = max{2, ⌈2/ε⌉}.

7 Conclusion

The paper adapts maximum-entropy sampling to RPP and obtains a better-than-3/2 approximation, while also transferring metric-TSP approximations to RPP and extending both guarantees to GRP.

  • A randomized polynomial-time (3/2 −ϵ)-approximation algorithm for RPP exists for an absolute constant ϵ > 10−36.
  • The guarantee can also be attained deterministically relative to RPP-LP using conditional expectation.
  • For every fixed ε > 0, an α-approximation algorithm for metric TSP yields an (α + ε)-approximation algorithm for RPP.
  • The same guarantees apply to GRP because RPP and GRP can be related by a cost-preserving reduction using zero-cost required leaf edges.

A LP-relative consequences

The subdivision transformation preserves LP feasibility and cost sufficiently to transfer metric-TSP approximation guarantees to RPP relative to RPP-LP.

  • The subdivision transformation is compatible with the LP relaxations.
  • An RPP-LP solution extends to a feasible TSP-LP solution by retaining connector values, assigning one to path edges, and zero to remaining edges.
  • Cut feasibility follows because paths crossing a cut twice contribute at least two, while otherwise the cut projects to a nontrivial subset of the original vertices.
  • The construction preserves the relevant cost bound, giving LTSP(Ik) ≤ L when x is chosen as an optimal RPP-LP solution.
  • An α-approximation for metric TSP therefore yields an RPP closed walk of cost at most (α+ε)L for every fixed ε > 0.

A.1 Equality of the integrality gaps

The preprocessed RPP-LP and metric-TSP subtour LP have equal worst-case integrality gaps, established through reductions in both directions that preserve costs and optima.

  • The two relaxations have the same worst-case integrality gap: γRPP = γTSP, and this gap is strictly below 3/2.
  • For an RPP instance, the subdivision transformation and LP transfer imply OPTRPP(J) ≤ γTSP L in the limit, hence γRPP ≤ γTSP.
  • A metric-TSP instance becomes an RPP instance by splitting each vertex into two copies joined by a zero-cost required edge and adding metric-cost connector edges.
  • Contracting the required edges maps feasible RPP walks to TSP tours, while TSP tours expand back, so the optimum values are equal.
  • The reverse LP mapping is cost preserving: TSP variables lift by assigning xuv/4 to each corresponding connector edge, with cut feasibility handled by required pairs and TSP cut constraints.
  • Metric-TSP integrality-gap ratios are reproduced exactly by RPP instances, establishing γTSP ≤ γRPP.
Loading 2608.27607v1…