Abstract
Given an undirected graph \(G=(V,E;w,p)\) with a depot \(r\in V\) and an integer \(k\in {{\mathbb {Z}}}^{+}\), each edge \(e\in E\) has a weight \(w(e)\in {{\mathbb {R}}}^{+}\) and a penalty \(p(e)\in {\mathbb R}^{+}_{0}\), where the weights satisfy the triangle inequality, we consider two types of restricted k-Chinese postman problems with penalties. (1) The restricted min–max k-Chinese postman problem with penalties (MM-RPCPP) is asked to find a set of k tours starting from r and collectively covering all vertices, such that the maximum tour weight plus the total penalty paid for the uncovered edges is minimized. (2) The restricted min-sum k-Chinese postman problem with penalties (MS-RPCPP) is asked to find a set of k tours satisfying the constraint mentioned above and that each edge appears in at most one tour and each tour contains at least one edge, such that the sum of weights of all tours plus the total penalty paid for the uncovered edges is minimized. In the paper, we design a combinatorial \((\frac{7}{2}-\frac{2}{k})\)-approximation algorithm to solve the MM-RPCPP. Furthermore, we present a combinatorial 2-approximation algorithm to solve the MS-RPCPP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aráoz, J., Fernández, E., Meza, O.: Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196, 886–896 (2009)
Aráoz, J., Fernández, E., Zoltan, C.: Privatized rural postman problems. Comput. Oper. Res. 33, 3432–3449 (2006)
Balas, E.: The prize collecting traveling salesman problem. Networks 19(6), 621–636 (1989)
Benavent, E., Campos, V., Corberán, A., Mota, E.: The capacitated arc routing problem: lower bounds. Networks 22, 669–690 (1992)
Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993)
Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973)
Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7(2), 178–193 (1978)
Frieze, A.M.: An extension of Christofides heuristic to the \(k\)-person travelling salesman problem. Discret. Appl. Math. 6, 79–83 (1983)
Glover, F., Klingman, D.: Finding minimum spanning trees with a fixed number of links at a node. In: Combinatorial Programming: Methods and Applications (Roy, B., Ed.), pp. 191–201. Dondrecht-Holland (1975)
Goemans, M., Williamson, D.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296–317 (1995)
Guan, M.G.: Graphic programming using odd or even points (in Chinese). Acta Math. Sinica 10, 263–266 (1960)
Karlin, A., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 32–45. Association for Computing Machinery, New York, USA (2021)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2018)
Pearn, W.L.: Solvable cases of the \(k\)-person Chinese postman problem. Oper. Res. Lett. 16, 241–244 (1994)
Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
Zhu, H.T., Pan, P.X.: The restricted Chinese postman problems with penalties. Oper. Res. Lett. 49, 851–854 (2021)
Acknowledgements
The authors are all grateful to an associate editor and all reviewers for their insightful comments and for their suggested changes that improve the presentation greatly.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Pan, P., Zhu, H. Approximation algorithms for the restricted k-Chinese postman problems with penalties. Optim Lett 18, 307–318 (2024). https://doi.org/10.1007/s11590-023-01992-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-023-01992-z