Smoothed analysis of local search for the maximum-cut problem

DOI10.1145/3011870MaRDI QIDQ4962657zbMATH OpenOpenAlexWikidataFDO

Authors Michael Etscheid, Heiko Röglin

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3011870

zbMATH Keywords

local searchmaximum-cut problemsmoothed analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Smoothed Analysis of Local Search for the Maximum-Cut Problem
• Local max-cut in smoothed polynomial time
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Settling the complexity of local max-cut (almost) completely
• Smoothed analysis of local search algorithms

Cited in

(26)

• Smoothed analysis for tensor methods in unsupervised learning
• Phase transition of degeneracy in minor-closed families
• Settling the complexity of local max-cut (almost) completely
• Smoothed Performance Guarantees for Local Search
• Smoothed analysis of local search algorithms
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Integer Linear Programs and Local Search for Max-Cut
• Local max-cut in smoothed polynomial time
• Smoothed Analysis of Local Search
• Improving the Smoothed Complexity of FLIP for Max Cut Problems
• Smoothing the Gap Between NP and ER
• Smoothed complexity of local max-cut and binary max-CSP
• Improving the smoothed complexity of FLIP for max cut problems
• Local optima of the Sherrington-Kirkpatrick Hamiltonian
• Smoothed Analysis of Local Search for the Maximum-Cut Problem
• The smoothed complexity of policy iteration for Markov decision processes
• Pattern reconstruction with restricted Boltzmann machines
• Node-max-cut and the complexity of equilibrium in linear weighted congestion games
• On the smoothed complexity of combinatorial local search
• Worst-case and smoothed analysis of the hartigan-Wong method for k-means clustering
• Minimum stable cut and treewidth
• Local Max-Cut on sparse graphs
• Complexity of local search for Euclidean clustering problems
• Settling the complexity of Nash equilibrium in congestion games
• Minimum stable cut and treewidth
• Experimental evaluation of a local search approximation algorithm for the multiway cut problem

This page was built for publication: Smoothed analysis of local search for the maximum-cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962657)