Abstract
Howard's algorithm is a fifty-year old generally applicable algorithm for sequential decision making in face of uncertainty. It is routinely used in practice in numerous application areas that are so important that they usually go by their acronyms, e.g., OR, AI, and CAV. While Howard's algorithm is generally recognized as fast in practice, until recently, its worst case time complexity was poorly understood. However, a surge of results since 2009 has led us to a much more satisfactory understanding of the worst case time complexity of the algorithm in the various settings in which it applies. In this talk, we shall survey these recent results and the open problems that remains.
| Original language | English |
|---|---|
| Title of host publication | Mathematical and Engineering Methods in Computer Science : 8th International Doctoral Workshop, MEMICS 2012, Znojmo, Czech Republic, October 25-28, 2012, Revised Selected Papers |
| Editors | Antonín Kučera |
| Number of pages | 4 |
| Publisher | Springer VS |
| Publication date | 2013 |
| Pages | 53-56 |
| ISBN (Print) | 9783642360442 |
| ISBN (Electronic) | 978-3-642-36046-6 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | Mathematical and Engineering Methods in Computer Science - Znojmo, Czech Republic Duration: 25 Oct 2013 → 28 Oct 2013 Conference number: 8 |
Conference
| Conference | Mathematical and Engineering Methods in Computer Science |
|---|---|
| Number | 8 |
| Country/Territory | Czech Republic |
| City | Znojmo |
| Period | 25/10/2013 → 28/10/2013 |
| Series | Lecture Notes in Computer Science |
|---|---|
| Volume | 7721 |
| ISSN | 0302-9743 |