Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Value Approximation:
TR02-070 | 13th December 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.

more >>>

TR06-155 | 15th December 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

ISSN 1433-8092 | Imprint