NDLI: Quantitative stochastic parity games

Please wait, while we are loading the content...

Succinct ordinal trees with level-ancestor queries

Finding a long directed cycle

Variable length path coupling

Who says you have to look at the input?: the brave new world of sublinear computing

Complexity classification of network information flow problems

Approximation schemes for multidimensional packing

Special edges, and approximating the smallest directed k-edge connected spanning subgraph

Retroactive data structures

Improved upper bounds for 3-SAT

A faster distributed protocol for constructing a minimum spanning tree

A time efficient Delaunay refinement algorithm

Adaptive sampling for quickselect

Minimum moment Steiner trees

Quantum computing

Interpolation search for non-independent data

Buffer minimization using max-coloring

Trade-offs on the location of the core node in a network

When indexing equals compression: experiments with compressing suffix arrays and applications

Dimension reduction for ultrametrics

Frugality in path auctions

Computing equilibria for congestion games with (im)perfect information

Quasiconvex analysis of backtracking algorithms

Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs

How random is the human genome?

Complexities for generalized models of self-assembly

Point containment in the integer hull of a polyhedron

Non-migratory online deadline scheduling on multiprocessors

On broadcasting in heterogenous networks

Randomized pursuit-evasion with limited visibility

On the diameter of the symmetric group: polynomial bounds

Compact representations of ordered sets

A new algorithm for normal dominance constraints

Linear phase transition in random linear constraint satisfaction problems

An improved data stream algorithm for frequency moments

New approximability and inapproximability results for 2-dimensional Bin Packing

On colorings of squares of outerplanar graphs

Proximity Mergesort: optimal in-place sorting in the cache-oblivious model

Locally satisfiable formulas

Experimental analysis of dynamic all pairs shortest path algorithms

Almost-Delaunay simplices: nearest neighbor relations for imprecise points

Fast mixing for independent sets, colorings and other models on trees

Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs

Dynamizing static algorithms, with applications to dynamic trees and history independence

On minimizing the total flow time on multiple machines

On the convergence time of a path-vector protocol

Approximate Nearest Neighbor under edit distance via product metrics

Randomized k-server algorithms for growth-rate bounded graphs

An exact subexponential-time lattice algorithm for Asian options

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates

Navigating nets: simple algorithms for proximity search

Equivalence of local treewidth and linear local treewidth and its algorithmic applications

Invadable self-assembly: combining robustness with efficiency

Covering minimum spanning trees of random subgraphs

The maximum latency of selfish routing

End-to-end packet-scheduling in wireless ad-hoc networks

Fault-tolerant gathering algorithms for autonomous mobile robots

The power of basis selection in fourier sampling: hidden subgroup problems in affine groups

Tight bounds for the partial-sums problem

Rank-maximal matchings

Quantitative stochastic parity games

Efficient estimation algorithms for neighborhood variance and other moments

On rectangle packing: maximizing benefits

Detecting short directed cycles using rectangular matrix multiplication and dynamic programming

The number of bit comparisons used by Quicksort: an average-case analysis

A stronger bound on Braess's Paradox

Graph decomposition and a greedy algorithm for edge-disjoint paths

Output-sensitive construction of the union of triangles

Slow mixing of Glauber dynamics for the hard-core model on the hypercube

Approximation schemes for Metric Bisection and partitioning

Caching queues in memory buffers

Matrix rounding and approximation

Tabulation based 4-universal hashing with applications to second moment estimation

Fast approximate pattern matching with few indels via embeddings

The pure literal rule threshold and cores in random hypergraphs

Structural and algorithmic aspects of massive social networks

Algorithms for infinite huffman-codes

Approximating the two-level facility location problem via a quasi-greedy approach

Hole and antihole detection in graphs

On contract-and-refine transformations between phylogenetic trees

A characterization of easily testable induced subgraphs

Minimizing migrations in fair multiprocessor scheduling of persistent tasks

Routing and scheduling in multihop wireless networks with time-varying channels

Approximate classification via earthmover metrics

Simultaneous diophantine approximation with excluded primes

The Bloomier filter: an efficient data structure for static support lookup tables

Network failure detection and graph connectivity

On distributions computable by random walks on graphs

Optimal space lower bounds for all frequency moments

Optimal online bounded space multidimensional packing

Approximating Minimum Max-Stretch spanning Trees on unweighted graphs

Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time

Multicommodity facility location

Models of greedy algorithms for graph problems

An optimal randomized algorithm for maximum Tukey depth

Probabilistic analysis of knapsack core algorithms

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks

LAND: stretch (1 + ε) locality-aware networks for DHTs

A general approach to online network optimization problems

Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem

Lyndon words with a fixed standard right factor

Efficient algorithms for bichromatic separability

A determinant-based algorithm for counting perfect matchings in a general graph

A certifying algorithm for the consecutive-ones property

A maiden analysis of Longest Wait First

Testing bipartiteness of geometric intersection graphs

Reconstructing strings from random traces

Bipartite roots of graphs

The wake-up problem in multi-hop radio networks

Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ

Facility location with Service Installation Costs

Constructing finite field extensions with large order elements

Meldable RAM priority queues and minimum directed spanning trees

The directed circular arrangement problem

Exponential bounds for DPLL below the satisfiability threshold

Optimal routing in Chord

Windows scheduling as a restricted version of Bin Packing

Approximate distance oracles for unweighted graphs in Õ $(n^{2})$ time

The hyperring: a low-congestion deterministic data structure for distributed environments

SRPT optimally utilizes faster machines to minimize flow time

The list partition problem for graphs

Minimizing the stabbing number of matchings, trees, and triangulations

Torpid mixing of simulated tempering on the Potts model

Correlation Clustering: maximizing agreements via semidefinite programming

A note on the nearest neighbor in growth-restricted metrics

Approximate local search in combinatorial optimization

Competitive analysis of organization networks or multicast acknowledgement: how much to wait?

Compression boosting in optimal linear time using the Burrows-Wheeler Transform

On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems

On the number of rectangular partitions

Generic quantum Fourier transforms

A deterministic near-linear time algorithm for finding minimum cuts in planar graphs

Finding dominators revisited: extended abstract

Improved bounds on sorting with length-weighted reversals

Two tricks to triangulate chordal probe graphs in polynomial time

A fast approximation scheme for fractional covering problems with variable upper bounds

Fair and efficient router congestion control

On finding a guard that sees most and a shop that sells most

Polynomial interpolation from multiples

Quantitative stochastic parity games

Content Provider	ACM Digital Library
Author	Jurdziński, Marcin Henzinger, Thomas A. Chatterjee, Krishnendu
Abstract	We study perfect-information stochastic parity games. These are two-player nonterminating games which are played on a graph with turn-based probabilistic transitions. A play results in an infinite path and the conflicting goals of the two players are ω-regular path properties, formalized as parity winning conditions. The qualitative solution of such a game amounts to computing the set of vertices from which a player has a strategy to win with probability 1 (or with positive probability). The quantitative solution amounts to computing the value of the game in every vertex, i.e., the highest probability with which a player can guarantee satisfaction of his own objective in a play that starts from the vertex.For the important special case of one-player stochastic parity games (parity Markov decision processes) we give polynomial-time algorithms both for the qualitative and the quantitative solution. The running time of the qualitative solution is O(d · $m^{3/2})$ for graphs with m edges and d priorities. The quantitative solution is based on a linear-programming formulation.For the two-player case, we establish the existence of optimal pure memoryless strategies. This has several important ramifications. First, it implies that the values of the games are rational. This is in contrast to the concurrent stochastic parity games of de Alfaro et al.; there, values are in general algebraic numbers, optimal strategies do not exist, and ε-optimal strategies have to be mixed and with infinite memory. Second, the existence of optimal pure memoryless strategies together with the polynomial-time solution forone-player case implies that the quantitative two-player stochastic parity game problem is in NP ∩ co-NP. This generalizes a result of Condon for stochastic games with reachability objectives. It also constitutes an exponential improvement over the best previous algorithm, which is based on a doubly exponential procedure of de Alfaro and Majumdar for concurrent stochastic parity games and provides only ε-approximations of the values.
Starting Page	121
Ending Page	130
Page Count	10
File Format	PDF
ISBN	089871558X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-01-11
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in