|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2007 | Copyright 2007 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |