Abstract
The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of \(\frac{21}{40}\). In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Babayev, D.A., Bell, G.I., Nuriyev, U.G.: The Bandpass Problem: Combinatorial Optimization and Library of Problems. Journal of Combinatorial Optimization 18, 151–172 (2009)
Barvinok, A., Johnson, D.S., Woeginger, G.J., Woodroofe, R.: The Maximum Traveling Salesman Problem Under Polyhedral Norms. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 195–201. Springer, Heidelberg (1998)
Bell, G.I., Babayev, D.A.: Bandpass Problem. In: Annual INFORMS Meeting, Denver, CO, USA (2004)
Chen, Z.-Z., Nagoya, T.: Improved Approximation Algorithms for Metric Max TSP. Journal of Combinatorial Optimization 13, 321–336 (2007)
Chen, Z.-Z., Okamoto, Y., Wang, L.: Improved deterministic approximation algorithms for Max TSP. Information Processing Letters 95, 333–342 (2005)
Chen, Z.-Z., Wang, L.: An Improved Randomized Approximation Algorithm for Max TSP. Journal of Combinatorial Optimization 9, 401–432 (2005)
Gabow, H.: Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs. Ph.D. Thesis, Department of Computer Science, Stanford University, Stanford, California (1973)
Gabow, H.: An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 448–456. ACM (1983)
Hassin, R., Rubinstein, S.: An Approximation Algorithm for the Maximum Traveling Salesman Problem. Information Processing Letters 67, 125–130 (1998)
Hassin, R., Rubinstein, S.: Better Approximations for Max TSP. Information Processing Letters 75, 181–186 (2000)
Hassin, R., Rubinstein, S.: A 7/8-Approximation Approximations for Metric Max TSP. Information Processing Letters 81, 247–251 (2002)
Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. Journal of the ACM 52, 602–626 (2005)
Kostochka, A.V., Serdyukov, A.I.: Polynomial Algorithms with the Estimates \(\frac{3}{4}\) and \(\frac{5}{6}\) for the Traveling Salesman Problem of Maximum. Upravlyaemye Sistemy 26, 55–59 (1985) (in Russian)
Kowalik, L., Mucha, M.: Deterministic 7/8-Approximation for the Metric Maximum TSP. Theor. Comput. Sci. 410, 5000–5009 (2009)
Lin, G.: On the Bandpass Problem. Journal of Combinatorial Optimization 22, 71–77 (2011)
Paluch, K., Mucha, M., Mądry, A.: A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 298–311. Springer, Heidelberg (2009)
Serdyukov, A.I.: An Algorithm with an Estimate for the Traveling Salesman Problem of Maximum. Upravlyaemye Sistemy 25, 80–86 (1984) (in Russian)
Tarjan, R.E.: Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM 225, 215–225 (1975)
Tong, W., Goebel, R., Ding, W., Lin, G.: An Improved Approximation Algorithm for the Bandpass Problem. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 351–358. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, ZZ., Wang, L. (2012). An Improved Approximation Algorithm for the Bandpass-2 Problem. In: Lin, G. (eds) Combinatorial Optimization and Applications. COCOA 2012. Lecture Notes in Computer Science, vol 7402. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31770-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-31770-5_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31769-9
Online ISBN: 978-3-642-31770-5
eBook Packages: Computer ScienceComputer Science (R0)