NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT

DOI10.15807/JORSJ.46.178zbMATH Open1049.90077OpenAlexW2153689539MaRDI QIDQ4446321FDOQ4446321

Tomomi Matsui, Shiro Matuura

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

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

zbMATH Keywords

combinatorial optimizationnonlinear programmingalgorithm

Mathematics Subject Classification ID

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

Cited In (6)

• Title not available (Why is that?)
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• On the directed cut cone and polytope
• Semidefinite programming based approaches to the break minimization problem
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Title not available (Why is that?)

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)