NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT

DOI10.15807/JORSJ.46.178MaRDI QIDQ4446321zbMATHOpenAlexFDO

Authors Shiro Matuura, Tomomi Matsui

Publication date 22 March 2004

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15807/jorsj.46.178

zbMATH Keywords

combinatorial optimizationnonlinear programmingalgorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22)

Recommendations

• scientific article; zbMATH DE number 2086914
• scientific article; zbMATH DE number 1833408
• Approximation algorithms for the maximum satisfiability problem
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cited in

(7)

• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• On the directed cut cone and polytope
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• scientific article; zbMATH DE number 1833408 (Why is no real title available?)
• Semidefinite programming based approaches to the break minimization problem
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT

This page was built for publication: NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4446321)