Re-optimization of constraint satisfaction problems with predicates of arity two

MaRDI QIDQ4899322zbMATH OpenFDO

Authors V. O. Mykhajlyuk, I. V. Sergienko

Publication date 8 January 2013

zbMATH Keywords

approximation algorithmconstraint satisfaction problemunique game conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• Reoptimization of constraint satisfaction problems with approximation resistant predicates
• Near-optimal algorithms for unique games
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems

Cited in

(3)

• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
• Reoptimization of constraint satisfaction problems with approximation resistant predicates

This page was built for publication: Re-optimization of constraint satisfaction problems with predicates of arity two

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