Abstract: In this paper, we address the k-Chinese postman problem under interdiction budget constraints (the k-CPIBC problem, for short), which is a further generalization of the k-Chinese postman problem and has many practical applications in real life. Specifically, given a weighted graph \begin{document}$ G=(V,E;w,c;v_{1}) $\end{document} equipped with a weight function \begin{document}$ w:E\rightarrow {\mathbb {R}}^{+} $\end{document} that satisfies the triangle inequality, an interdiction cost function \begin{document}$ c:E\rightarrow {\mathbb {Z}}^{+} $\end{document}, a fixed depot \begin{document}$ v_{1}\in V $\end{document}, an integer \begin{document}$ k\in {\mathbb {Z}}^{+} $\end{document} and a budget \begin{document}$ B\in {\mathbb {N}} $\end{document}, we are asked to find a subset \begin{document}$ S_{k}\subseteq E $\end{document} such that \begin{document}$ c(S_{k})=\sum _{e\in S_{k}}c(e)\leqslant B $\end{document} and that the subgraph \begin{document}$ G\backslash S_{k} $\end{document} is connected, the objective is to minimize the value \begin{document}$ \min _{\mathcal{C}_{E\backslash S_{k}}} \max \{w(C_{i})\,\vert \,C_{i}\in \mathcal{C}_{E\backslash S_{k}}\} $\end{document} among such all aforementioned subsets \begin{document}$ S_{k} $\end{document}, where \begin{document}$ \mathcal{C}_{E\backslash S_{k}} $\end{document} is a set of k-tours (of \begin{document}$ G\backslash S_{k} $\end{document}) starting and ending at the depot \begin{document}$ v_{1} $\end{document}, jointly traversing each edge in \begin{document}$ G\backslash S_{k} $\end{document} at least once, and \begin{document}$ w(C_{i})=\sum _{e\in C_{i}}w(e) $\end{document} for each tour \begin{document}$ C_{i}\in \mathcal{C}_{E\backslash S_{k}} $\end{document}. We obtain the following main results: (1) Given an \begin{document}$ \alpha $\end{document}-approximation algorithm to solve the minimization knapsack problem, we design an \begin{document}$ (\alpha +\beta ) $\end{document}-approximation algorithm to solve the k-CPIBC problem, where \begin{document}$ \beta $\end{document} \begin{document}$ = $\end{document} \begin{document}$ \frac{7}{2}-\frac{1}{k}-\lfloor \frac{1}{k}\rfloor $\end{document}. (2) We present a \begin{document}$ \beta $\end{document}-approximation algorithm to solve the special version of the k-CPIBC problem, where c(e) \begin{document}$ \equiv $\end{document} 1 for each edge e in G and \begin{document}$ \beta $\end{document} is defined in (1).

Key words: Combinatorial optimization, Arc routing, k-Chinese postman problem, Interdiction, Approximation algorithms