On the Smoothed Complexity of Combinatorial Local Search

References

• [1] Aarts E, Lenstra JK, eds. (1997) Local Search in Combinatorial Optimization (John Wiley & Sons Ltd, Hoboken, NJ).Google Scholar
• [2] Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J. ACM 55(6):25.Crossref, Google Scholar
• [3] Angel O, Bubeck S, Peres Y, Wei F (2017) Local max-cut in smoothed polynomial time. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 429–437.Google Scholar
• [4] Applegate DL, Bixby RE, Chvatál V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• [5] Beier R, Vöcking B (2006) Typical properties of winners and losers in discrete optimization. SIAM J. Comput. 35(4):855–881.Crossref, Google Scholar
• [6] Bhalgat A, Chakraborty T, Khanna S (2010) Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. Proc. 11th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 73–82.Google Scholar
• [7] Bibak A, Carlson C, Chandrasekaran K (2021) Improving the smoothed complexity of FLIP for max cut problems. ACM Trans. Algorithms 17(3):19.Crossref, Google Scholar
• [8] Bobkov SG, Chistyakov GP (2014) Bounds on the maximum of the density for sums of independent random variables. J. Math. Sci. 199(2):100–106.Crossref, Google Scholar
• [9] Boodaghians S, Kulkarni R, Mehta R (2020) Smoothed efficient algorithms and reductions for network coordination games. Proc. 11th Innovations in Theoret. Comput. Sci. Conf., Leibniz International Proceedings in Informatics, vol. 151 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 73:1–73:15.Google Scholar
• [10] Brandts-Longtin A (2018) Smoothed analysis of max-k-sat. Master’s thesis, McGill University, Montreal.Google Scholar
• [11] Cai Y, Daskalakis C (2011) On minmax theorems for multiplayer games. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 217–234.Google Scholar
• [12] Chandra B, Karloff H, Tovey C (1999) New results on the old k-opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6):1998–2029.Crossref, Google Scholar
• [13] Chen X, Guo C, Vlatakis-Gkaragkounis EV, Yannakakis M, Zhang X (2020) Smoothed complexity of local max-cut and binary max-CSP. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1052–1065.Google Scholar
• [14] Cook WJ (2012) In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University Press, Princeton and Oxford).Google Scholar
• [15] Daskalakis C, Papadimitriou C (2011) Continuous local search. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 790–804.Google Scholar
• [16] Dumrauf D, Monien B (2013) On the PLS-complexity of maximum constraint assignment. Theoret. Comput. Sci. 469:24–52.Crossref, Google Scholar
• [17] Dumrauf D, Süß T (2010) On the complexity of local search for weighted standard set problems. Preprint, submitted April 6, https://arxiv.org/abs/1004.0871.Google Scholar
• [18] Dumrauf D, Süß T (2010) On the complexity of local search for weighted standard set problems. Ferreira F, Löwe B, Mayordomo E, Mendes Gomes L, eds. Programs, Proofs, Processes (Springer, Berlin, Heidelberg), 132–140.Crossref, Google Scholar
• [19] Elsässer R, Tscheuschner T (2011) Settling the complexity of local max-cut (almost) completely. Aceto L, Henzinger M, Sgall J, eds. Automata, Languages, and Programming (Springer, Berlin, Heidelberg), 171–182.Crossref, Google Scholar
• [20] Engels C, Manthey B (2009) Average-case approximation ratio of the 2-opt algorithm for the TSP. Oper. Res. Lett. 37(2):83–84.Crossref, Google Scholar
• [21] Englert M, Röglin H, Vöcking B (2014) Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica 68(1):190–264.Crossref, Google Scholar
• [22] Englert M, Röglin H, Vöcking B (2017) Smoothed analysis of the 2-opt algorithm for the general TSP. ACM Trans. Algorithms 13(1):1549–6325.Crossref, Google Scholar
• [23] Etscheid M, Röglin H (2015) Smoothed analysis of the squared Euclidean maximum-cut problem. Algorithms—ESA 2015 (Springer, Berlin, Heidelberg), 509–520.Crossref, Google Scholar
• [24] Etscheid M, Röglin H (2017) Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms 13(2):25.Crossref, Google Scholar
• [25] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Proc. 36th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 604–612.Google Scholar
• [26] Fearnley J, Gordon S, Mehta R, Savani R (2020) Unique end of potential line. J. Comput. System Sci. 114:1–35.Crossref, Google Scholar
• [27] Gairing M, Savani R (2019) Computing stable outcomes in symmetric additively separable hedonic games. Math. Oper. Res. 44(3):1101–1121.Link, Google Scholar
• [28] Garey MR, Johnson DS (1990) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, Houndmills).Google Scholar
• [29] Giannakopoulos Y (2024) A smoothed FPTAS for equilibria in congestion games. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 401–413.Google Scholar
• [30] Gutin G, Punnen AP, eds. (2007) The Traveling Salesman Problem and Its Variations (Springer, New York).Crossref, Google Scholar
• [31] Halmos PR (1974) Measure Theory, Graduate Texts in Mathematics, vol. 18 (Springer, New York).Google Scholar
• [32] Johnson DS, McGeoch LA (1997) The traveling salesman problem: A case study. Aarts E, Lenstra JK, eds. Local Search in Combinatorial Optimization (John Wiley, Hoboken, NJ).Google Scholar
• [33] Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J. Comput. System Sci. 37(1):79–100.Crossref, Google Scholar
• [34] Kanellakis PC, Papadimitriou CH (1980) Local search for the asymmetric traveling salesman problem. Oper. Res. 28(5):1086–1099.Link, Google Scholar
• [35] Klauck H (1996) On the hardness of global and local approximation. Proc. Fifth Scandinavian Workshop Algorithm Theory (Springer, Berlin, Heidelberg), 88–99.Google Scholar
• [36] Krentel MW (1989) Structure in locally optimal solutions. Proc. 30th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 216–221.Google Scholar
• [37] Krentel MW (1990) On finding and verifying locally optimal solutions. SIAM J. Comput. 19(4):742–749.Crossref, Google Scholar
• [38] Manthey B, van Rhijn J (2023) Improved smoothed analysis of 2-opt for the Euclidean TSP. Iwata S, Kakimura N, eds. Proc. 34th Internat. Sympos. Algorithms Comput., Leibniz International Proceedings in Informatics, vol. 283 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 52:1–52:16.Google Scholar
• [39] Manthey B, Veenstra R (2013) Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise. Algorithms and Computation (Springer, Berlin), 579–589.Crossref, Google Scholar
• [40] Michiels W, Korst J, Aarts E (2007) Theoretical Aspects of Local Search (Springer, Berlin, Heidelberg).Google Scholar
• [41] Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• [42] Monien B, Tscheuschner T (2010) On the power of nodes of degree four in the local max-cut problem. Proc. Seventh Internat. Conf. Algorithms Complexity (Springer, Berlin, Heidelberg), 264–275.Google Scholar
• [43] Orlin JB, Punnen AP, Schulz AS (2004) Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5):1201–1214.Crossref, Google Scholar
• [44] Röglin H (2008) The complexity of Nash equilibria, local optima, and Pareto-optimal solutions. PhD thesis, RWTH Aachen University, Aachen, Germany.Google Scholar
• [45] Röglin H, Vöcking B (2007) Smoothed analysis of integer programming. Math. Programming 110(1):21–56.Crossref, Google Scholar
• [46] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
• [47] Roughgarden T (2016) Pure Nash equilibria and PLS-completeness. Twenty Lectures on Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 261–278.Crossref, Google Scholar
• [48] Roughgarden T, ed. (2021) Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK).Google Scholar
• [49] Schäffer AA, Yannakakis M (1991) Simple local search problems that are hard to solve. SIAM J. Comput. 20(1):56–87.Crossref, Google Scholar
• [50] Schwartzman G (2024) Local max-cut on sparse graphs. Proc. 32nd Annual Eur. Sympos. Algorithms, Leibniz International Proceedings in Informatics, vol. 308 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 98:1–98:6.Google Scholar
• [51] Spielman DA, Teng SH (2004) Smoothed analysis of algorithms. J. ACM 51(3):385–463.Crossref, Google Scholar
• [52] Spielman DA, Teng SH (2009) Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10):76–84.Crossref, Google Scholar
• [53] Svensson O, Tarnawski J, Végh LA (2020) A constant-factor approximation algorithm for the asymmetric traveling salesman problem. J. ACM 67(6):37.Crossref, Google Scholar
• [54] Szeider S (2011) The parameterized complexity of k-flip local search for SAT and MAX SAT. Discrete Optim. 8(1):139–145.Crossref, Google Scholar
• [55] Yagiura M, Ibaraki T (1999) Analyses on the 2 and 3-flip neighborhoods for the MAX SAT. J. Comb. Optim. 3(1):95–114.Crossref, Google Scholar
• [56] Yannakakis M (1997) Computational complexity. Aarts E, Lenstra JK, eds. Local Search in Combinatorial Optimization (John Wiley, Hoboken, NJ).Google Scholar
• [57] Zhong X (2020) On the approximation ratio of the k-opt and Lin-Kernighan algorithm for metric and graph TSP. Proc. 28th Annual Eur. Sympos. Algorithms (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 83:1–83:13.Google Scholar