|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
22 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games | | Carlo Comin
; Romeo Rizzi
; | | Date: |
6 Sep 2016 | | Abstract: | This study strengthens the links between Mean Payoff Games (MPG{s}) and
Energy Games (EG{s}). Firstly, we offer a faster $O(|V|^2|E|W)$
pseudo-polynomial time and $Theta(|V|+|E|)$ space deterministic algorithm for
solving the Value Problem and Optimal Strategy Synthesis in MPG{s}. This
improves the best previously known estimates on the pseudo-polynomial time
complexity to: [ O(|E|log |V|) + ThetaBig(sum_{vin
V} exttt{deg}_{Gamma}(v)cdotell_{Gamma}(v)Big) = O(|V|^2|E|W), ] where
$ell_{Gamma}(v)$ counts the number of times that a certain energy-lifting
operator $delta(cdot, v)$ is applied to any $vin V$, along a certain
sequence of Value-Iterations on reweighted EG{s}; and
$ exttt{deg}_{Gamma}(v)$ is the degree of $v$. This improves significantly
over a previously known pseudo-polynomial time estimate, i.e.
$Thetaig(|V|^2|E|W + sum_{vin
V} exttt{deg}_{Gamma}(v)cdotell_{Gamma}(v)ig)$ citep{CR15, CR16}, as
the pseudo-polynomiality is now confined to depend solely on $ell_Gamma$.
Secondly, we further explore on the relationship between Optimal Positional
Strategies (OPSs) in MPG{s} and Small Energy-Progress Measures (SEPMs) in
reweighted EG{s}. It is observed that the space of all OPSs,
$ exttt{opt}_{Gamma}Sigma^M_0$, admits a unique complete decomposition in
terms of extremal-SEPM{s} in reweighted EG{s}. This points out what we called
the "Energy-Lattice $mathcal{X}^*_{Gamma}$ associated to
$ exttt{opt}_{Gamma}Sigma^M_0$". Finally, it is offered a pseudo-polynomial
total-time recursive procedure for enumerating (w/o repetitions) all the
elements of $mathcal{X}^*_{Gamma}$, and for computing the corresponding
partitioning of $ exttt{opt}_{Gamma}Sigma^M_0$. | | Source: | arXiv, 1609.1517 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER