Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

DOI10.1016/S0166-218X(02)00402-XzbMath1051.68078OpenAlexW2036185701WikidataQ56288411 ScholiaQ56288411MaRDI QIDQ1408377

Jens Gramm, Rolf Niedermeier, Peter Rossmanith, Edward A. Hirsch

Publication date: 15 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00402-x

zbMATH Keywords

maximum cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (25)

Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ Optimal 2-constraint satisfaction via sum-product algorithms ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ New upper bounds for the problem of maximal satisfiability ⋮ An upper (lower) bound for Max (Min) CSP ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ A tighter upper bound for random MAX \(2\)-SAT ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ Exact Algorithms for MAX-SAT ⋮ A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ A \(2^{|E|/4}\)-time algorithm for MAX-CUT ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ An Empirical Study of MAX-2-SAT Phase Transitions ⋮ Improving exact algorithms for MAX-2-SAT

Uses Software

• MAX-2-SAT

Cites Work

• A simplified NP-complete MAXSAT problem
• Solving satisfiability in less than \(2^ n\) steps
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Automata, languages and programming. 26th international colloquium, ICALP `99. Prague, Czech Republic, July 11--15, 1999. Proceedings
• On fixed-parameter tractability and approximability of NP optimization problems
• New worst-case upper bounds for SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• An improved exponential-time algorithm for k -SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On the Approximation of Maximum Satisfiability
• New Upper Bounds for Maximum Satisfiability
• Some optimal inapproximability results
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.