Approximation algorithms for the maximum 2-peripatetic salesman problem

A. A. Ageev, A. E. Baburin, and E. Kh. Gimadi, “A 3/4-Approximation Algorithm for Finding Two Disjoint Hamiltonian Cycles of Maximum Weight,” Diskret. Anal. Issled. Oper. Ser. 1, 13(2), 11–20 (2006) [J. Appl. Indust. Math. 1 (2), 142–147 (2007)].

E. Kh. Gimadi, Yu. V. Glazkov, and A. N. Glebov, “Approximation Algorithms for Solving the 2-Peripatetic Salesman Problem on a Complete Graph with Edge Weights 1 and 2,” Diskret. Anal. Issled. Oper. Ser. 2, 14(2), 41–61 (2007) [J. Appl. Indust. Math. 3 (1), 46–60 (2009)].

A. N. Glebov and D. Zh. Zambalaeva, “A Polynomial Algorithm with Approximation Ratio 7/9 for the Maximum Two Peripatetic Salesmen Problem,” Diskret. Anal. Issled. Oper. 16(4), 17–48 (2011) [J. Appl. Indust. Math. 6 (1), 69–89 (2012)].

M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, 1979; Mir, Moscow, 1982).

A. I. Serdyukov, “An Algorithm with an Estimate for the Traveling Salesman Problem of the Maximum,” Upravlyaemye Sistemy (Inst. Mat., Novosibirsk), No. 25, 80–86 (1984).

A. E. Baburin, F. D. Croce, E. Kh. Gimadi, Y. V. Glazkov, and V. Th. Paschos, “Approximation Algorithms for the 2-Peripatetic Salesman Problem with Edge Weights 1 and 2,” Discrete Appl. Math. 157(9), 1988–1992 (2009).

J. B. J. M. De Kort, “A Branch and Bound Algorithm for Symmetric 2-Peripatetic Salesman Problems,” European J. Oper. Res. 10(2), 229–243 (1993).

H. N. Gabow, “An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems,” in Proceedings of the 15th Annual ACM Symposium: Theory of Computing (Boston, April 25–27, 1983) (ACM Press, New York, 1983), pp. 448–456.

A. N. Glebov, A. V. Gordeeva, and D. Zh. Zambalaeva, “7/5-Approximation Algorithm for a 2-Peripatetic Salesman Problem on Minimum with Different Weight Functions Valued 1 and 2,” Discrete Appl. Math. (submitted) (2010).

G. Gutin and A. P. Punnen, The Traveling Salesman Problem and Its Variations (Kluwer Acad. Publ., Dordrecht, 2002).

J. Krarup, “The Peripatetic Salesman and Some Related Unsolved Problems,” in Combinatorial Programming: Methods and Applications (Kluwer Acad. Publ., Dordrecht, 1975), pp. 173–178.

E. L. Lawler, J. K. Lenstra, A.H. G. Rinnooy Kan, and D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, Chichester, 1985).

C. H. Papadimitriou and M. Yannakakis, “The Traveling Salesman Problem with Distances One and Two,” Math. Oper. Res. 18(1), 1–11 (1993).