We present an approximation algorithm that achieves a ratio strictly smaller than $3/2$ for the Rural Postman Problem (RPP). The key idea is to adapt the maximum‑entropy distribution sampling technique, originally developed by Karlin, Klein, and Oveis Gharan for the metric Traveling Salesman Problem (TSP), to the RPP setting. The method constructs a maximum‑entropy distribution on a metric graph, samples a near‑optimal tour, and then adjusts the tour to ensure that all required edges are traversed.
We also note that for any fixed $\varepsilon>0$, an $\alpha$-approximation algorithm for the metric TSP immediately yields an $(\alpha+\varepsilon)$-approximation algorithm for the RPP. This implication is already implicit in Lampis's work on the inapproximability of the TSP, though it has not been explicitly highlighted before.
Blogger's Review: This paper illustrates the power of transferring sophisticated sampling techniques from TSP to the more general RPP, tightening the known approximation bound and opening new avenues for future research.