报告题目：Approximation algorithms for solving the vertex-traversing-constrained mixed  Chinese postman problem

报告人：云南大学 李建平教授

报告时间：3月19日  4：00-5：00

报告地点：五教5306

摘要：

In this talk, we consider the vertex-traversing-constrained mixed Chinese postman problem (the VtcMCP problem), which is a further generalization of the Chinese postman problem,  and this new problem has many practical applications in real life.  Specifically, given a connected mixed graph $G=(V, E\cup A; w,b)$ with length function $w(\cdot)$  on edges and arcs and traversal function $b(\cdot)$ on vertices, we are asked to determine a tour traversing each link ({\it i.e.}, either edge or arc) at least once and each vertex $v$ at most $b(v)$ times, the objective is to minimize the total length of such a tour, where $n=|V|$ is the number of vertices and $m=|E\cup A|$ is the number of links of $G$, respectively.

We obtain the following four main results. (1) Given any two constants $\beta \geq 1$ and $\alpha \geq 1$, we prove that there is no polynomial-time algorithm with approximation ratios $(1,\beta)$ or $(\alpha, 1)$ for solving the VtcMCP problem, where an $(h,k)$-approximation algorithm for solving the VtcMCP problem is one algorithm that produces a solution with violating the vertex-traversing constraints by at most a ratio of $h$ and with costing at most $k$ times the optimal value; (2) We design a $(3, 2)$-approximation algorithm ${\cal A}$  to solve the VtcMCP problem in time $O(m^{2}\log n)$; (3) We prove the fact that this algorithm ${\cal A}$ in (2) is indeed an exact algorithm to optimally solve the VtcMCP problem for the case $E=\emptyset$; (4) We present an exact algorithm  to optimally solve the VtcMCP problem in time $O(m^{3})$  for the case $A=\emptyset$.