ECCC-Report TR06-155https://eccc.weizmann.ac.il/report/2006/155Comments and Revisions published for TR06-155en-usFri, 02 Mar 2007 00:00:00 +0200
Revision 1
| Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP |
Wenceslas Fernandez de la Vega,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2006/155#revision1We 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.
Fri, 02 Mar 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2006/155#revision1
Paper TR06-155
| Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP |
Wenceslas Fernandez de la Vega,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2006/155We 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.
Fri, 15 Dec 2006 14:00:00 +0200https://eccc.weizmann.ac.il/report/2006/155