Weconsidertheproblemofdesigningapproximationschemesforthe values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [−1, 1] admit additive fully-polynomial approxima- tion schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of design- ing 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.
A note on the approximation of mean-payoff games.
GENTILINI, Raffaella
2011
Abstract
Weconsidertheproblemofdesigningapproximationschemesforthe values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [−1, 1] admit additive fully-polynomial approxima- tion schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of design- ing 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
