Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints

Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li

doi:10.1007/s40305-023-00488-y

Journal of the Operations Research Society of China >

2025 , Vol. 13 >Issue 2: 535 - 554

DOI: https://doi.org/10.1007/s40305-023-00488-y

Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints

Expand

1. School of Mathematics and Statistics, Yunnan University, Kunming 650504, Yunnan, China;
2. School of Mathematics and Physics, Beijing University of Chemical Technology, Beijing 100190, China

Received date: 2022-11-29

Revised date: 2023-03-29

Online published: 2025-07-07

Supported by

These authors are supported by the National Natural Science Foundation of China (Nos. 11861075, 12101593) and Project for Innovation Team (Cultivation) of Yunnan Province (No. 202005AE-160006). Peng-Xiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund (No. 2020Y0040), Jun-Ran Lichen is also supported by Fundamental Research Funds for the Central Universities (No. buctrc202219), and Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province (No. K264202011820).

Fold

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

Cite this article

Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li . Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints[J]. Journal of the Operations Research Society of China, 2025 , 13(2) : 535 -554 . DOI: 10.1007/s40305-023-00488-y

References

[1] Guan, M.G.: Graphic programming using odd or even points. Acta Math. Sin. 10, 263-266 (1960). (in Chinese)
[2] Edmonds, J.: Maximum matching and a polyhedron with (0,1)-vertices. J. Res. Natl. Bureau Stand. B 69, 125-130 (1965)
[3] Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88-124 (1973)
[4] Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7(2), 178-193 (1978)
[5] Beullens, P., Muyldermans, L., Cattrysse, D., Oudheusden, D.V.: A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147(3), 629-643 (2003)
[6] Corberán, Á., Martí, R., Sanchis, J.M.: A GRASP heuristic for the mixed Chinese postman problem. Eur. J. Oper. Res. 142(1), 70-80 (2002)
[7] Ding, H.L., Li, J.P., Lih, K.W.: Approximation algorithms for solving the constrained arc routing problem in mixed graphs. Eur. J. Oper. Res. 239(1), 80-88 (2014)
[8] Jozefowiez, N., Semet, F., Talbi, E.G.: Multi-objective vehicle routing problems. Eur. J. Oper. Res. 189, 293-309 (2008)
[9] Lysgaard, J., Wøhlk, S.: A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236, 800-810 (2014)
[10] Mourão, M.C., Amado, L.: Heuristic method for a mixed capacitated arc routing problem: a refuse collection application. Eur. J. Oper. Res. 160, 139-153 (2005)
[11] Zachariadis, E.E., Kiranoudis, C.T.: Local search for the undirected capacitated arc routing problem with profits. Eur. J. Oper. Res. 210(2), 358-367 (2011)
[12] Ghare, P.M., Montgomery, D.C., Turner, W.C.: Optimal interdiction policy for a flow network. Naval Res. Logist. Q. 18, 37-45 (1971)
[13] Assimakopoulos, N.: A network interdiction model for hospital infection control. Comput. Biol. Med. 17(6), 413-422 (1987)
[14] Wood, R.K.: Deterministic network interdiction. Math. Comput. Model. 17(2), 1-18 (1993)
[15] Church, R.L., Scaparra, M.P., Middleton, R.S.: Identifying critical infrastructure: the median and covering facility interdiction problems. Ann. Assoc. Am. Geogr. 94(3), 491-502 (2004)
[16] Salmeron, J., Wood, K., Baldick, R.: Analysis of electric grid security under terrorist threat. IEEE Trans. Power Syst. 19(2), 905-912 (2004)
[17] Lin, K.C., Chern, M.S.: The most vital edges in the minimum spanning tree problem. Inform. Process. Lett. 45(1), 25-31 (1993)
[18] Frederickson, G.N., Solis-Oba, R.: Increasing the weight of minimum spanning trees. J. Algorithms 33(2), 244-266 (1999)
[19] Bazgan, C., Toubaline, S., Vanderpooten, D.: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation. J. Comb. Optim. 26(1), 178-189 (2013)
[20] Zenklusen, R.: An O(1)-approximation for minimum spanning tree interdiction. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 709-728 (2015)
[21] Linhares, A., Swamy, C.: Improved algorithms for MST and metric-TSP interdiction. In: Proceedings of 44th International Colloquium on Automata, Languages, and Programming (ICALP) Art.No 32, 14pp (2017) https://doi.org/10.48550/arXiv.1706.00034
[22] Zenklusen, R.: Matching interdiction. Discrete Appl. Math. 158(15), 1676-1690 (2010)
[23] Dinitz, M., Gupta, A.: Packing interdiction and partial covering problems. In: Proceedings of International Conference on Integer Programming and Combinatorial Optimization (IPCO’13), pp. 157-168 (2013)
[24] Pan, F., Schild, A.: Interdiction problems on planar graphs. Discrete Appl. Math. 198, 215-231 (2016)
[25] Golden, B.: A problem in network interdiction. Naval Res. Logist. Q. 25(4), 711-713 (1978)
[26] Ball, M.O., Golden, B.L., Vohra, R.V.: Finding the most vital arcs in a network. Oper. Res. Lett. 8(2), 73-76 (1989)
[27] Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97-111 (2002)
[28] Phillips, C.A.: The network inhibition problem. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC’93), pp. 776-785 (1993)
[29] Zenklusen, R.: Network flow interdiction on planar graphs. Discrete Appl. Math. 158(13), 1441-1455 (2010)
[30] Zenklusen, R.: Connectivity interdiction. Oper. Res. Lett. 42(6-7), 450-454 (2014)
[31] Armon, A., Zwick, U.: Multicriteria global minimum cuts. Algorithmica 46, 15-16 (2006)
[32] Johnson, D.S., Niemi, K.A.: On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8, 1-14 (1983)
[33] Smith, J.C., Song, Y.J.: A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3), 797-811 (2020)
[34] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269-271 (1959)
[35] Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389-1401 (1957)
[36] Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)
[37] Gabow, H.N.: Data structures for weighted matching and extensions to b-matching and f-factors. ACM Trans. Algorithms 14(3), Art. 39, 80pp (2018)
[38] Fisher, M.L.: A polynomial algorithm for the degree-constrained minimum K-tree problem. Oper. Res. 42(4), 775-779 (1994)
[39] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)
[40] Güntzer, M.M., Jungnickel, D.: Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Oper. Res. Lett. 26(2), 55-66 (2000)
[41] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
[42] Csirik, J., Frenk, J.B.G., Labbé, M., Zhang, S.: Heuristics for the 0-1 min-knapsack problem. Acta Cybern. 10(1-2), 15-20 (1991)
[43] Carnes, T., Shmoys, D.B.: Primal-dual schema for capacitated covering problems. Math. Program. 153(2), 289-308 (2015)
[44] Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388. Graduate School of Industrial Administration, Carnegie Mellon University (1976)

Options

Abstract

Outlines

模态框（Modal）标题

Abstract

Cite this article

References