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
Revision #1 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Accepted on: 2nd March 2007 00:00
Downloads: 117
Keywords:
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
TR06-155 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 15th December 2006 14:00
Downloads: 107
Keywords:
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.