A note on the approximation of mean-payoff games |
| |
Authors: | Raffaella Gentilini |
| |
Affiliation: | Department of Mathematics and Computer Science, University of Perugia, Via Vanvitelli 1, I-06123, Perugia, Italy |
| |
Abstract: | We consider the problem of designing approximation schemes for the values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on −1,1] admit additive fully-polynomial approximation schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of designing additive/relative approximation schemes for general mean-payoff games (i.e. with no constraint on their edge-weights) is P-time equivalent to determining their exact solution. |
| |
Keywords: | Mean-payoff games Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|