标题： 一种改进的容量弧路由问题近似算法 显示英文标题

标题： An Improved Approximation Algorithm for the Capacitated Arc Routing Problem

摘要： 容量弧路由问题（CARP），由Golden和Wong于1981年提出，是运筹学中的一个重要弧路由问题，它推广了著名的容量车辆路由问题（CVRP）。当每个客户都有单位需求时，Jansen在1993年给出的CARP最佳已知近似比仍然是$\frac{5}{2}-\frac{1.5}{k}$，其中$k$表示车辆容量。基于最近在近似CVRP方面的进展，我们通过提出一个$(\frac{5}{2}-\Theta(\frac{1}{\sqrt{k}}))$近似算法改进了这一结果，据我们所知，这是对Jansen界限的首次改进。 显示英文摘要

摘要： The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacitated Vehicle Routing Problem (CVRP). When every customer has a unit demand, the best known approximation ratio for CARP, given by Jansen in 1993, remains $\frac{5}{2}-\frac{1.5}{k}$, where $k$ denotes the vehicle capacity. Based on recent progress in approximating CVRP, we improve this result by proposing a $(\frac{5}{2}-\Theta(\frac{1}{\sqrt{k}}))$-approximation algorithm, which to the best of our knowledge constitutes the first improvement over Jansen's bound.