Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

DOI10.1007/b11961zbMath1279.68108OpenAlexW4298253479MaRDI QIDQ5900948

Alexander D. Scott, Gregory B. Sorkin

Publication date: 26 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b11961

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ A Spectral Method for MAX2SAT in the Planted Solution Model ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ Average-case analysis for the MAX-2SAT problem ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications

This page was built for publication: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques