Dynamical systems theory and algorithms for NP-hard problems. (English) Zbl 1528.37072
Junge, Oliver (ed.) et al., Advances in dynamics, optimization and computation. A volume dedicated to Michael Dellnitz on the occasion of his 60th birthday. Cham: Springer. Stud. Syst. Decis. Control 304, 183-206 (2020).
Summary: This article surveys the burgeoning area at the intersection of dynamical systems theory and algorithms for NP-hard problems. Traditionally, computational complexity and the analysis of non-deterministic polynomial-time (NP)-hard problems have fallen under the purview of computer science and discrete optimization. However, over the past few years, dynamical systems theory has increasingly been used to construct new algorithms and shed light on the hardness of problem instances. We survey a range of examples that illustrate the use of dynamical systems theory in the context of computational complexity analysis and novel algorithm construction. In particular, we summarize a) a novel approach for clustering graphs using the wave equation partial differential equation, b) invariant manifold computations for the traveling salesman problem, c) novel approaches for building quantum networks of Duffing oscillators to solve the MAX-CUT problem, d) applications of the Koopman operator for analyzing optimization algorithms, and e) the use of dynamical systems theory to analyze computational complexity.
For the entire collection see [Zbl 1445.37003].
For the entire collection see [Zbl 1445.37003].
MSC:
| 37M99 | Approximation methods and numerical treatment of dynamical systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W40 | Analysis of algorithms |
| 90C27 | Combinatorial optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
computational complexity; dynamical systems theory; NP-hardness; heuristic algorithms; combinatorial optimizationReferences:
| [1] | Poincaré, H.: Sur le problème des trois corps et les équations de la dynamique. Acta Mathe. 13, A3-A270 (1890) · JFM 22.0907.01 |
| [2] | Turing, A.: On computable problems with an application to the entscheidungsproblem. Proc. Lond. Math. Soc. 2, 42 (1936) · Zbl 0016.09701 |
| [3] | Church, A.: A set of postulates for the foundation of logic. Ann. Math. 33, 346-366 (1932) · Zbl 0004.14507 · doi:10.2307/1968337 |
| [4] | Strogatz, S.H.: Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering. CRC Press, Boca Raton (2018) · doi:10.1201/9780429492563 |
| [5] | Walleczek, J. (ed.): Self-Organized Biological Dynamics and Nonlinear Control: Toward Understanding Complexity, Chaos and Emergent Function in Living Systems. Cambridge University Press (2006) |
| [6] | Kevrekidis, I.G., Schmidt, L.D., Aris, R.: On the dynamics of periodically forced chemical reactors. Chem. Eng. Commun. 30(6), 323-330 (1984) · doi:10.1080/00986448408911136 |
| [7] | Holmes, P., Lumley, J.L., Berkooz, G., Rowley, C.W.: Turbulence, Coherent Structures, Dynamical Systems and Symmetry. Cambridge University Press, Cambridge (2012) · Zbl 1251.76001 · doi:10.1017/CBO9780511919701 |
| [8] | Liu, W.M., Hethcote, H.W., Levin, S.A.: Dynamical behavior of epidemiological models with nonlinear incidence rates. J. Math. Biol. 25(4), 359-380 (1987) · Zbl 0621.92014 · doi:10.1007/BF00277162 |
| [9] | Dellnitz, M., Junge, O.: Set oriented numerical methods for dynamical systems. Handb. Dyn. Syst. 2, 221-264 (2002) · Zbl 1036.37030 · doi:10.1016/S1874-575X(02)80026-1 |
| [10] | Mezić, I.: Analysis of fluid flows via spectral properties of the Koopman operator. Annu. Rev. Fluid Mech. 45, 357-378 (2013) · Zbl 1359.76271 · doi:10.1146/annurev-fluid-011212-140652 |
| [11] | Hummer, G., Kevrekidis, I.G.: Coarse molecular dynamics of a peptide fragment: free energy, kinetics, and long-time dynamics computations. J. Chem. Phys. 118(23), 10762-10773 (2003) · doi:10.1063/1.1574777 |
| [12] | Hasselblatt, B., Katok, A. (eds.) Handbook of Dynamical Systems. Elsevier, Amsterdam (2002) · Zbl 1013.00016 |
| [13] | Lorenz, E.N.: Deterministic nonperiodic flow. J. Atmos. Sci. 20(2), 130-141 (1963) · Zbl 1417.37129 · doi:10.1175/1520-0469(1963)020<0130:DNF>2.0.CO;2 |
| [14] | Morse, M., Hedlund, G.A.: Symbolic dynamics. Am. J. Math. 60(4), 815-866 (1938) · Zbl 0019.33502 · doi:10.2307/2371264 |
| [15] | Guckenheimer, J., Holmes, P.: Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields, vol. 42. Springer, New York (2013) · Zbl 0515.34001 |
| [16] | Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence \(O (1/k^2)\). In: Doklady an Ussr, vol. 269, pp. 543-547 (1983) |
| [17] | Su, W., Boyd, S., Candes, E.: A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. In: Advances in Neural Information Processing Systems, pp. 2510-2518 (2014) |
| [18] | Wibisono, A., Wilson, A.C., Jordan, M.I.: A variational perspective on accelerated methods in optimization. Proc. Natl. Acad. Sci. 113(47), E7351-E7358 (2016) · Zbl 1404.90098 · doi:10.1073/pnas.1614734113 |
| [19] | Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151-158 (1971) · Zbl 0253.68020 |
| [20] | Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85-103. Springer, Boston (1972) · Zbl 1467.68065 |
| [21] | Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44(10), 2245-2269 (1965) · Zbl 0136.14705 · doi:10.1002/j.1538-7305.1965.tb04146.x |
| [22] | Cook, W.J.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton (2011) |
| [23] | Peikert, C.: A decade of lattice cryptography. Found. Trends® Theoret. Comput. Sci. 10(4), 283-424 (2016) · Zbl 1391.94788 |
| [24] | Klus, S., Sahai, T.: A spectral assignment approach for the graph isomorphism problem. Inf. Inference J. IMA 7(4), 689-706 (2018) · Zbl 1470.05156 |
| [25] | Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106-130 (2000) · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2 |
| [26] | Applegate, D., Bixby, R., Chvatal, V., Cook, W. Concorde TSP Solver (2006) |
| [27] | Sahai, T., Speranzon, A., Banaszuk, A.: Wave equation based algorithm for distributed eigenvector computation. In: 49th IEEE Conference on Decision and Control (CDC), pp. 7308-7315, December 2010 |
| [28] | Sahai, T., Speranzon, A., Banaszuk, A.: Hearing the clusters of a graph: a distributed algorithm. Automatica 48(1), 15-24 (2012) · Zbl 1244.93016 · doi:10.1016/j.automatica.2011.09.019 |
| [29] | Sahai, T., Ziessler, A., Klus, S., Dellnitz, M.: Continuous relaxations for the traveling salesman problem. Nonlinear Dyn. 97(4), 2003-2022 (2019) · Zbl 1430.37126 · doi:10.1007/s11071-019-05092-5 |
| [30] | Goto, H., Tatsumura, K., Dixon, A.R.: Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Sci. Adv. 5(4), eaav2372 (2019) · Zbl 1411.90295 |
| [31] | Dietrich, F., Thiem, T.N., Kevrekidis, I.G.: On the Koopman operator of algorithms. arXiv preprint arXiv:1907.10807 (2019) · Zbl 1437.47048 |
| [32] | Ercsey-Ravasz, M., Toroczkai, Z.: Optimization hardness as transient chaos in an analog approach to constraint satisfaction. Nat. Phys. 7(12), 966-970 (2011) · doi:10.1038/nphys2105 |
| [33] | Varga, M., Sumi, R., Toroczkai, Z., Ercsey-Ravasz, M.: Order-to-chaos transition in the hardness of random Boolean satisfiability problems. Phys. Rev. E 93(5), 052211 (2016) · doi:10.1103/PhysRevE.93.052211 |
| [34] | Even, S.: Graph Algorithms. Cambridge University Press, UK (2011) · Zbl 0441.68072 |
| [35] | Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2009) · Zbl 1187.68679 |
| [36] | Von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395-416 (2007) · doi:10.1007/s11222-007-9033-z |
| [37] | Wagner, D., Wagner, F.: Between min cut and graph bisection. In: International Symposium on Mathematical Foundations of Computer Science, pp. 744-750. Springer, Berlin (1993) · Zbl 0925.05053 |
| [38] | Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore and London (1996) · Zbl 0865.65009 |
| [39] | Kempe, D., McSherry, F.: A decentralized algorithm for spectral analysis. J. Comput. Syst. Sci. 74(1), 70-83 (2008) · Zbl 1131.68074 · doi:10.1016/j.jcss.2007.04.014 |
| [40] | Kac, M.: Can one hear the shape of a drum? Am. Math. Monthly 73(4P2), 1-23 (1966) · Zbl 0139.05603 |
| [41] | Klus, S., Sahai, T., Liu, C., Dellnitz, M.: An efficient algorithm for the parallel solution of high-dimensional differential equations. J. Comput. Appl. Math. 235(9), 3053-3062 (2011) · Zbl 1210.65145 · doi:10.1016/j.cam.2010.12.026 |
| [42] | Surana, A., Sahai, T., Banaszuk, A.: Iterative methods for scalable uncertainty quantification in complex networks. Int. J. Uncertain. Quantific. 2(4) (2012) · Zbl 07694400 |
| [43] | Englot, B., Sahai, T., Cohen, I.: Efficient tracking and pursuit of moving targets by heuristic solution of the traveling salesman problem. In: 52nd IEEE Conference on Decision and Control, pp. 3433-3438. IEEE, December 2013 |
| [44] | Gower, J.C., Dijksterhuis, G.B.: Procrustes Problems, vol. 3. Oxford University Press, New York (2004) · Zbl 1057.62044 · doi:10.1093/acprof:oso/9780198510581.001.0001 |
| [45] | Sahai, T., Klus, S., Dellnitz, M.: A Traveling Salesman Learns Bayesian Networks. arXiv preprint arXiv:1211.4888 (2012) |
| [46] | Schönemann, P.H.: On two-sided orthogonal Procrustes problems. Psychometrika 33(1), 19-33 (1968) · doi:10.1007/BF02289673 |
| [47] | Dellnitz, M., Hohmann, A.: The computation of unstable manifolds using subdivision and continuation. In: Nonlinear Dynamical Systems and Chaos, pp. 449-459. Birkhäuser, Basel (1996) · Zbl 0842.58064 |
| [48] | Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115-1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [49] | Glauber, R.J.: Time-dependent statistics of the Ising model. J. Math. Phys. 4(2), 294-307 (1963) · Zbl 0145.24003 · doi:10.1063/1.1703954 |
| [50] | Budisić, M., Mohr, R., Mezić, I.: Applied Koopmanism. Chaos Interdiscipl. J. Nonlinear Sci. 22(4), 047510 (2012) · Zbl 1319.37013 |
| [51] | Klus, S., Koltai, P., Schütte, C.: On the numerical approximation of the Perron-Frobenius and Koopman operator. arXiv preprint arXiv:1512.05997 (2015) · Zbl 1353.37154 |
| [52] | Williams, M.O., Kevrekidis, I.G., Rowley, C.W.: A data-driven approximation of the Koopman operator: extending dynamic mode decomposition. J. Nonlinear Sci. 25(6), 1307-1346 (2015) · Zbl 1329.65310 · doi:10.1007/s00332-015-9258-5 |
| [53] | Lusch, B., Kutz, J.N., Brunton, S.L.: Deep learning for universal linear embeddings of nonlinear dynamics. Nat. Commun. 9(1), 1-10 (2018) · doi:10.1038/s41467-018-07210-0 |
| [54] | Kutz, J.N., Brunton, S.L., Brunton, B.W., Proctor, J.L.: Dynamic Mode Decomposition: Data-driven Modeling of Complex Systems. Society for Industrial and Applied Mathematics (2016) · Zbl 1365.65009 |
| [55] | Dellnitz, M., Hohmann, A., Junge, O., Rumpf, M.: Exploring invariant sets and invariant measures. Chaos Interdiscipl. J. Nonlinear Sci. 7(2), 221-228 (1997) · Zbl 0938.37056 |
| [56] | Korda, M., Putinar, M., Mezić, I.: Data-driven spectral analysis of the Koopman operator. Appl. Comput. Harmonic Anal. (2018) · Zbl 1436.37093 |
| [57] | Molnár, B., Molnár, F., Varga, M., Toroczkai, Z., Ercsey-Ravasz, M.: A continuous-time MaxSAT solver with high analog performance. Nat. Commun. 9(1), 1-12 (2018) · doi:10.1038/s41467-018-07327-2 |
| [58] | Biere, A., Heule, M., van Maaren, H. (eds.) Handbook of Satisfiability, vol. 185. IOS Press, Amsterdam (2009) · Zbl 1183.68568 |
| [59] | Krentel, M.W.: The complexity of optimization functions. J. Comput. Syst. Sci. 36, 490-509 (1988) · Zbl 0652.68040 · doi:10.1016/0022-0000(88)90039-6 |
| [60] | Sahai, T. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
