Approximating Max kCSP using random restrictions

DOI10.1007/978-3-540-27821-4_14MaRDI QIDQ5313018zbMATH OpenOpenAlexFDO

Authors Gustav Hast

Publication date 25 August 2005

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

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximating MAX kCSP -- outperforming a random assignment with almost a linear factor
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• Approximating satisfiable satisfiability problems (extended abstract)
• Approximating satisfiable satisfiability problems

Cited in

(6)

• Approximating satisfiable satisfiability problems
• Positive linear programming, parallel approximation and PCP's
• scientific article; zbMATH DE number 2119703 (Why is no real title available?)
• Approximation algorithm for random MAX-kSAT
• Approximating MAX kCSP -- outperforming a random assignment with almost a linear factor
• Approximating satisfiable satisfiability problems (extended abstract)

This page was built for publication: Approximating Max \(k\)CSP using random restrictions

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