English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a deterministic algorithm, solving discounted games with $n$ nodesin $n^{O(1)}\cdot (2 + \sqrt{2})^n$-time. For bipartite discounted games ouralgorithm runs in $n^{O(1)}\cdot 2^n$-time. Prior to our work no deterministicalgorithm running in time $2^{o(n\log n)}$ regardless of the discount factorwas known.  We call our approach polyhedral value iteration. We rely on a well-known factthat the values of a discounted game can be found from the so-called optimalityequations. In the algorithm we consider a polyhedron obtained by relaxingoptimality equations. We iterate points on the border of this polyhedron bymoving each time along a carefully chosen shift as far as possible. Thiscontinues until the current point satisfies optimality equations.  Our approach is heavily inspired by a recent algorithm of Dorfman et al.(ICALP 2019) for energy games. For completeness, we present their algorithm interms of polyhedral value iteration. Our exposition, unlike the originalalgorithm, does not require edge weights to be integers and works for arbitraryreal weights.

Polyhedral value iteration for discounted games and energy games