↓ Skip to main content

Automata, Languages, and Programming

Overview of attention for book
Cover of 'Automata, Languages, and Programming'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Exact Weight Subgraphs and the k -Sum Conjecture
  3. Altmetric Badge
    Chapter 2 Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines
  4. Altmetric Badge
    Chapter 3 Tight Lower Bound for Linear Sketches of Moments
  5. Altmetric Badge
    Chapter 4 Optimal Partitioning for Dual Pivot Quicksort
  6. Altmetric Badge
    Chapter 5 Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
  7. Altmetric Badge
    Chapter 6 On the Extension Complexity of Combinatorial Polytopes
  8. Altmetric Badge
    Chapter 7 Algorithms for Hub Label Optimization
  9. Altmetric Badge
    Chapter 8 Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
  10. Altmetric Badge
    Chapter 9 Search-Space Size in Contraction Hierarchies
  11. Altmetric Badge
    Chapter 10 Time-Efficient Quantum Walks for 3-Distinctness
  12. Altmetric Badge
    Chapter 11 An Algebraic Characterization of Testable Boolean CSPs
  13. Altmetric Badge
    Chapter 12 Approximation Algorithms for the Joint Replenishment Problem with Deadlines
  14. Altmetric Badge
    Chapter 13 Sparse Suffix Tree Construction in Small Space
  15. Altmetric Badge
    Chapter 14 Tree Compression with Top Trees
  16. Altmetric Badge
    Chapter 15 Noncommutativity Makes Determinants Hard
  17. Altmetric Badge
    Chapter 16 Optimal Orthogonal Graph Drawing with Convex Bend Costs
  18. Altmetric Badge
    Chapter 17 Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
  19. Altmetric Badge
    Chapter 18 On the Complexity of Higher Order Abstract Voronoi Diagrams
  20. Altmetric Badge
    Chapter 19 A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
  21. Altmetric Badge
    Chapter 20 Direct Product via Round-Preserving Compression
  22. Altmetric Badge
    Chapter 21 How Hard Is Counting Triangles in the Streaming Model?
  23. Altmetric Badge
    Chapter 22 Online Checkpointing with Improved Worst-Case Guarantees
  24. Altmetric Badge
    Chapter 23 Exact and Efficient Generation of Geometric Random Variates and Random Graphs
  25. Altmetric Badge
    Chapter 24 Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
  26. Altmetric Badge
    Chapter 25 On Randomized Online Labeling with Polynomially Many Labels
  27. Altmetric Badge
    Chapter 26 Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
  28. Altmetric Badge
    Chapter 27 New Doubling Spanners: Better and Simpler
  29. Altmetric Badge
    Chapter 28 Maximum Edge-Disjoint Paths in k -Sums of Graphs
  30. Altmetric Badge
    Chapter 29 On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
  31. Altmetric Badge
    Chapter 30 Counting Matchings of Size k Is $\sharp$ W [1]-Hard
  32. Altmetric Badge
    Chapter 31 Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree
  33. Altmetric Badge
    Chapter 32 A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
  34. Altmetric Badge
    Chapter 33 Combining Binary Search Trees
  35. Altmetric Badge
    Chapter 34 The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
  36. Altmetric Badge
    Chapter 35 Clustering in the Boolean Hypercube in a List Decoding Regime
  37. Altmetric Badge
    Chapter 36 A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
  38. Altmetric Badge
    Chapter 37 Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
  39. Altmetric Badge
    Chapter 38 On the Power of Deterministic Mechanisms for Facility Location Games
  40. Altmetric Badge
    Chapter 39 ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
  41. Altmetric Badge
    Chapter 40 Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions
  42. Altmetric Badge
    Chapter 41 An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets
  43. Altmetric Badge
    Chapter 42 Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete
  44. Altmetric Badge
    Chapter 43 Dynamic Compressed Strings with Random Access
  45. Altmetric Badge
    Chapter 44 The Complexity of Planar Boolean #CSP with Complex Weights
  46. Altmetric Badge
    Chapter 45 Arthur-Merlin Streaming Complexity
  47. Altmetric Badge
    Chapter 46 Local Correctability of Expander Codes
  48. Altmetric Badge
    Chapter 47 On the Complexity of Broadcast Setup
  49. Altmetric Badge
    Chapter 48 On Model-Based RIP-1 Matrices
  50. Altmetric Badge
    Chapter 49 Robust Pseudorandom Generators
  51. Altmetric Badge
    Chapter 50 A Robust AFPTAS for Online Bin Packing with Polynomial Migration,
  52. Altmetric Badge
    Chapter 51 Small Stretch Pairwise Spanners
  53. Altmetric Badge
    Chapter 52 Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions
  54. Altmetric Badge
    Chapter 53 The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
  55. Altmetric Badge
    Chapter 54 Approximating Semi-matchings in Streaming and in Two-Party Communication
  56. Altmetric Badge
    Chapter 55 Full-Fledged Real-Time Indexing for Constant Size Alphabets
  57. Altmetric Badge
    Chapter 56 Arithmetic Circuit Lower Bounds via MaxRank
  58. Altmetric Badge
    Chapter 57 Model Checking Lower Bounds for Simple Graphs
  59. Altmetric Badge
    Chapter 58 The Complexity of Proving That a Graph Is Ramsey
  60. Altmetric Badge
    Chapter 59 An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,
  61. Altmetric Badge
    Chapter 60 A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
  62. Altmetric Badge
    Chapter 61 Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
  63. Altmetric Badge
    Chapter 62 Graph Reconstruction via Distance Oracles
  64. Altmetric Badge
    Chapter 63 Dual Techniques for Scheduling on a Machine with Varying Speed
  65. Altmetric Badge
    Chapter 64 Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms
  66. Altmetric Badge
    Chapter 65 No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem
  67. Altmetric Badge
    Chapter 66 A Composition Theorem for the Fourier Entropy-Influence Conjecture
  68. Altmetric Badge
    Chapter 67 Large Neighborhood Local Search for the Maximum Set Packing Problem
  69. Altmetric Badge
    Chapter 68 The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
  70. Altmetric Badge
    Chapter 69 The Complexity of Infinitely Repeated Alternating Move Games
  71. Altmetric Badge
    Chapter 70 Approximating the Diameter of Planar Graphs in Near Linear Time
  72. Altmetric Badge
    Chapter 71 Testing Linear-Invariant Function Isomorphism
Attention for Chapter 19: A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
Altmetric Badge

Citations

dimensions_citation
2 Dimensions

Readers on

mendeley
21 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
Chapter number 19
Book title
Automata, Languages, and Programming
Published by
Springer, Berlin, Heidelberg, July 2013
DOI 10.1007/978-3-642-39206-1_19
Book ISBNs
978-3-64-239205-4, 978-3-64-239206-1
Authors

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 21 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
United States 1 5%
Unknown 20 95%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 6 29%
Professor 4 19%
Student > Master 3 14%
Researcher 2 10%
Lecturer 1 5%
Other 1 5%
Unknown 4 19%
Readers by discipline Count As %
Computer Science 13 62%
Mathematics 1 5%
Physics and Astronomy 1 5%
Medicine and Dentistry 1 5%
Unknown 5 24%