Book Chapter

Approximating satisfiable satisfiability problems
Extended Abstract]

Luca Trevisan

Lecture Notes in Computer Science, 1997, Volume 1284, Algorithms — ESA '97, Pages 472-485

• Download PDF (1,000.0 KB)

Book Chapter

Approximability of NP-Optimization Problems

A. Steger

CMS Books in Mathematics, 2003, Recent Advances in Algorithms and Combinatorics, Pages 195-243

• Download PDF (687.7 KB)

Book Chapter

Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses

Venkatesan Guruswami

Lecture Notes in Computer Science, 2000, Volume 1913, Approximation Algorithms for Combinatorial Optimization, Pages 155-166

• Download PDF (255.9 KB)

Book Chapter

Approximating Max kCSP Using Random Restrictions

Gustav Hast

Lecture Notes in Computer Science, 2004, Volume 3122, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Pages 151-162

• Download PDF (210.8 KB)

Book Chapter

Generalised Integer Programming Based on Logically Defined Relations

Peter Jonsson and Gustav Nordh

Lecture Notes in Computer Science, 2006, Volume 4162, Mathematical Foundations of Computer Science 2006, Pages 549-560

• Download PDF (502.7 KB)

Book Chapter

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

Per Austrin and Subhash Khot

Lecture Notes in Computer Science, 2011, Volume 6755, Automata, Languages and Programming, Pages 474-485

• Download PDF (246.6 KB)

Book Chapter

On the Hardness of Approximating NP Witnesses

Uriel Feige, Michael Langberg and Kobbi Nissim

Lecture Notes in Computer Science, 2000, Volume 1913, Approximation Algorithms for Combinatorial Optimization, Pages 85-104

• Download PDF (221.0 KB)

Book Chapter

Exact Max 2-Sat : Easier and Faster

Martin Fürer and Shiva Prasad Kasiviswanathan

Lecture Notes in Computer Science, 2007, Volume 4362, SOFSEM 2007: Theory and Practice of Computer Science, Pages 272-283

• Download PDF (519.2 KB)