scientific article; zbMATH DE number 1263278
From MaRDI portal
Publication:4234151
zbMath0929.90071MaRDI QIDQ4234151
Michel X. Goemans, David P. Williamson
Publication date: 16 March 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
duality gaplinear programming relaxationworst-case analysismaximum satisfiability problem\({3\over 4}\)-approximation algorithm
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items (6)
Simultaneous Approximation of Constraint Satisfaction Problems ⋮ On dependent randomized rounding algorithms ⋮ Rounding algorithms for covering problems ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ Improved randomized approximation algorithms for lot-sizing problems ⋮ On dependent randomized rounding algorithms
This page was built for publication:
