Linear-programming design and analysis of fast algorithms for Max 2-CSP

DOI10.1016/j.disopt.2007.08.001zbMath1153.90505OpenAlexW2010651583MaRDI QIDQ2427689

Gregory B. Sorkin, Alexander D. Scott

Publication date: 14 May 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.08.001

zbMATH Keywords

exact algorithmsmeasure and conquerMax 2-CSPMax cutlinear-programming dualityMax 2-sat

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (18)

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ 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 ⋮ A modeling and computational study of the frustration index in signed networks ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Unnamed Item ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach ⋮ Unnamed Item ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds on the bisection width of 3- and 4-regular graphs
• A dichotomy theorem for maximum generalized satisfiability problems.
• Pathwidth of cubic graphs and exact algorithms
• Large induced degenerate subgraphs
• Network-based heuristics for constraint-satisfaction problems
• Tree clustering for constraint networks
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Counting models for 2SAT and 3SAT formulae
• An exact algorithm for MAX-CUT in sparse graphs
• The Approximability of Constraint Satisfaction Problems
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• A new approach to proving upper bounds for MAX-2-SAT
• New Upper Bounds for Maximum Satisfiability
• Gadgets, Approximation, and Linear Programming
• 3-coloring in time
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Exact Max 2-Sat: Easier and Faster
• An LP-Designed Algorithm for Constraint Satisfaction
• Automata, Languages and Programming
• Quasiconvex Analysis of Backtracking Algorithms
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Linear-programming design and analysis of fast algorithms for Max 2-CSP