Local search: is brute-force avoidable?
From MaRDI portal
Publication:439931
DOI10.1016/j.jcss.2011.10.003zbMath1244.68070OpenAlexW2165930352WikidataQ57359626 ScholiaQ57359626MaRDI QIDQ439931
Fedor V. Fomin, Daniel Lokshtanov, Michael R. Fellows, Saket Saurabh, Yngve Villanger, Frances A. Rosamond
Publication date: 17 August 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.003
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ On the complexity of restoring corrupted colorings ⋮ Can local optimality be used for efficient data reduction? ⋮ Local search: is brute-force avoidable? ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Parameterized dynamic cluster editing ⋮ Searching for better fill-in ⋮ Minimizing Rosenthal potential in multicast games ⋮ Data-driven inverse modelling through neural network (deep learning) and computational heat transfer ⋮ On the parameterized complexity of reconfiguration problems ⋮ On the parameterized complexity of consensus clustering ⋮ Parameterized Dynamic Cluster Editing ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Introduction to reconfiguration
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local search: is brute-force avoidable?
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Improved upper bounds for vertex cover
- Theoretical aspects of local search.
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- Linearity of grid minors in treewidth with applications through bidimensionality
- Graph minors. V. Excluding a planar graph
- How easy is local search?
- Graph minors. X: Obstructions to tree-decomposition
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XVI: Excluding a non-planar graph
- Diameter and treewidth in minor-closed graph families
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parametrized complexity theory.
- Local tree-width, excluded minors, and approximation algorithms
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- A constant factor approximation algorithm for a class of classification problems
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- On the Hardness of Losing Weight
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Note on the Convergence of Simulated Annealing Algorithms
- On the Complexity of Local Search for the Traveling Salesman Problem
- On Syntactic versus Computational Views of Approximability
- On Local Search and Placement of Meters in Networks
- A Method for Solving Traveling-Salesman Problems
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
