我们提出了一种近似算法，使得农村邮递员问题（Rural Postman Problem, RPP）的近似比严格小于 $3/2$。该算法的核心思路是将 Karlin、Klein 与 Oveis Gharan 为度量旅行商问题（Metric TSP）设计的最大熵分布抽样技术迁移到 RPP 上。具体做法是先在满足度量性质的图上构造最大熵分布，然后通过抽样得到一条近似最优的遍历路径，最后对必须经过的边进行适当的修正，以保证所有必经边都被覆盖。
我们还观察到，对于任意固定的正数 $\varepsilon>0$，如果存在一个 $\alpha$-近似算法能够解决度量 TSP，则可以直接得到一个 $(\alpha+\varepsilon)$-近似算法用于 RPP。这一蕴含已经在 Lampis 对旅行商问题不可近似性的研究中隐含出现，只是此前并未显式表述。
博主点评：该工作展示了跨问题技术迁移的潜力，尤其是将 TSP 的高阶抽样方法成功应用到更一般的 RPP，进一步压缩了已知的近似下界，为后续研究提供了新的思路。