Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-155 | 2nd March 2007 00:00

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

RSS-Feed

Abstract:

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 for constructing approximate solutions of the above optimization problems.


Paper:

TR06-155 | 15th December 2006 00:00

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


Abstract:

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 for constructing approximate solutions of the above optimization problems.



ISSN 1433-8092 | Imprint