Abstract
We survey complexity and approximability results for certain families of geometric optimization problems. We explain a generic approximation approach for maximization problems that is built around norms with polyhedral unit balls, and we pose a multitude of open problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arkin, E.M., Chiang, Y.J., Mitchell, J.S.B., Skiena, S., Yang, T.C.: On the maximum scatter traveling salesperson problem. SIAM J. Comput. 29, 515–544 (1999)
Baburin, A.E., Gimadi, E.K.: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space. Proc. Steklov Inst. Math. 270, 1–13 (2011)
Bandelt, H.J., Crama, Y., Spieksma, F.C.R.: Approximation algorithms for multi-dimensional assignment problems with decomposable costs. Discrete Appl. Math. 49, 25–50 (1994)
Barvinok, A.: Two algorithmic results for the traveling salesman problem. Math. Oper. Res. 21, 65–84 (1996)
Barvinok, A.I., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum travelling salesman problem. J. ACM 50, 641–664 (2003)
Birnbaum, B.E., Goldman, K.J.: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 55, 42–59 (2009)
Borodin, A., Jain, A., Lee, H.C., Ye, Y.: Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms 13, 41:1–41:25 (2017)
Burkard, R.E., van Dal, R., Deineko, V.G., van der Veen, J., Woeginger, G.J.: Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev. 40, 496–546 (1998)
Burkard, R.E., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)
Burkard, R.E., Rudolf, R., Woeginger, G.J.: Three-dimensional axial assignment problems with decomposable cost coefficients. Discrete Appl. Math. 65, 123–140 (1996)
Cevallos, A., Eisenbrand, F., Morell, S.: Diversity maximization in doubling metrics. In: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC-2018) (2018)
Cevallos, A., Eisenbrand, F., Zenklusen, R.: Max-sum diversity via convex programming. In: Proceedings of the 32nd Symposium on Computational Geometry (SoCG-2016), pp. 26:1–26:14 (2016)
Crama, Y., Spieksma, F.C.R.: Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur. J. Oper. Res. 60, 273–379 (1992)
Custic, A., Klinz, B., Woeginger, G.J.: Geometric versions of the 3-dimensional assignment problem under general norms. Discrete Optim. 18, 38–55 (2015)
De Brey, M.J.D., Volgenant, A.: Well-solved cases of the 2-peripatetic salesman problem. Optimization 39, 275–293 (1997)
Deineko, V.G., Woeginger, G.J.: The maximum travelling salesman problem on symmetric Demidenko matrices. Discrete Appl. Math. 99, 413–425 (2000)
Dudycz, S., Marcinkowski, J., Paluch, K., Rybicki, B.: A 4/5 - approximation algorithm for the maximum traveling salesman problem. In: Eisenbrand, F., Koenemann, J. (eds.) IPCO 2017. LNCS, vol. 10328, pp. 173–185. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59250-3_15
Glebov, A.N., Zambalaeva, D.Z.: A polynomial algorithm with approximation ratio 7/9 for the maximum 2-peripatetic salesmen problem. J. Appl. Ind. Math. 6, 69–89 (2012)
Hassin, R., Rubinstein, S., Tamir, A.: Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21, 133–137 (1997)
Itai, A., Papadimitriou, C.H., Swarcfiter, J.L.: Hamiltonian paths in grid graphs. SIAM J. Comput. 11, 676–686 (1982)
Jansen, B.M.P.: Question posed at the ALGO-2018 conference held in Helsinki, Finland, 20–24 August 2018 (2018)
Kalmanson, K.: Edgeconvex circuits and the travelling salesman problem. Can. J. Math. 27, 1000–1010 (1975)
Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37, 27–35 (1991)
Kowalik, L., Mucha, M.: Deterministic \(7/8\)-approximation for the metric maximum TSP. Theor. Comput. Sci. 410, 5000–5009 (2009)
Kozma, L., Mömke, T: Maximum scatter TSP in doubling metrics. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2017), pp. 143–153 (2017)
Krarup, J.: The peripatetic salesman and some related unsolved problems. In: Roy, B. (ed.) Combinatorial Programming: Methods and Applications, vol. 19, pp. 173–178. Springer, Dordrecht (1975). https://doi.org/10.1007/978-94-011-7557-9_8
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Travelling Salesman Problem. Wiley, Chichester (1985)
Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC-2017), pp. 954–961 (2017)
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)
Pferschy, U., Rudolf, R., Woeginger, G.J.: Some geometric clustering problems. Nordic J. Comput. 1, 246–263 (1994)
Polyakovskiy, S., Spieksma, F.C.R., Woeginger, G.J.: The three-dimensional matching problem in Kalmanson matrices. J. Comb. Optim. 26, 1–9 (2013)
Serdyukov, A.I.: An asymptotically optimal algorithm for the maximum travelling salesman problem in Euclidean space in finite-dimensional normed spaces. Upravlyaemye sistemy (Novosibirsk) 27, 79–87 (1987). (in Russian)
Serdyukov, A.I.: Asymptotic properties of optimal solutions of extremal permutation problems in finite-dimensional normed spaces. Metody Diskretnogo Analiza 51, 105–111 (1991). (in Russian)
Shenmaier, V.V.: Asymptotically optimal algorithms for geometric Max-TSP and Max-\(m\)-PSP. Discrete Appl. Math. 163, 214–219 (2014)
Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discrete Math. 4, 550–567 (1991)
Acknowledgement
This work is supported by the DFG RTG 2236 “UnRAVeL”. I thank Stefan Lendl for discussions, and I thank Thomas Erlebach for a number of comments that helped to improve the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Woeginger, G.J. (2018). Some Easy and Some Not so Easy Geometric Optimization Problems. In: Epstein, L., Erlebach, T. (eds) Approximation and Online Algorithms. WAOA 2018. Lecture Notes in Computer Science(), vol 11312. Springer, Cham. https://doi.org/10.1007/978-3-030-04693-4_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-04693-4_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04692-7
Online ISBN: 978-3-030-04693-4
eBook Packages: Computer ScienceComputer Science (R0)