Revision #1 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski

Accepted on: 2nd March 2007 00:00

Downloads: 2949

Keywords:

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.

TR06-155 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski

Publication: 15th December 2006 14:00

Downloads: 2606

Keywords:

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.