Analyses on the 2 and 3-flip neighborhoods for the MAX SAT

DOI10.1023/A:1009873324187zbMath0955.90119OpenAlexW1587355033MaRDI QIDQ1304388

Mutsunori Yagiura, Toshihide Ibaraki

Publication date: 4 March 2001

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009873324187

zbMATH Keywords

local searchneighborhoodSATMAX SAT

Mathematics Subject Classification ID

Search theory (90B40) Combinatorial optimization (90C27)

Related Items (11)

Relaxation heuristics for the set multicover problem with generalized upper bound constraints ⋮ Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints ⋮ Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ Efficient local search algorithms for the linear ordering problem ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ A hybrid tabu search/branch \& bound approach to solving the generalized assignment problem ⋮ Solving weighted MAX-SAT via global equilibrium search ⋮ The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT

Uses Software

• Walksat

This page was built for publication: Analyses on the 2 and 3-flip neighborhoods for the MAX SAT