Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2007 Copyright 2007 Universität Bonn, Institut für Informatik, Abt. V
89108

05.03.2007

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP (Revised Version)
W. Fernandez de la Vega and Marek Karpinski
[Download PostScript] [Download PDF]

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any r ≥ 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.

Last Change: 11/05/14 at 10:38:09
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope