DROPS

Document

Enumeration in Data Management (Dagstuhl Seminar 19211)

Authors: Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt

Published in: Dagstuhl Reports, Volume 9, Issue 5 (2019)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 19211 "Enumeration in Data Management". The goal of the seminar was to bring together researchers from various fields of computer science, including the Databases, Computational Logic, and Algorithms communities, and establish the means of collaboration towards considerable progress on the topic. Specifically, we aimed at understanding the recent developments, identifying the important open problems, and initiating collaborative efforts towards solutions thereof. In addition, we aimed to build and disseminate a toolkit for data-centric enumeration problems, including algorithmic techniques, proof techniques, and important indicator problems. Towards the objectives, the seminar included tutorials on the topic, invited talks, presentations of open problems, working groups on the open problems, discussions on platforms to compile the community knowledge, and the construction of various skeletons of such compilations.

Cite as

Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt. Enumeration in Data Management (Dagstuhl Seminar 19211). In Dagstuhl Reports, Volume 9, Issue 5, pp. 89-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{boros_et_al:DagRep.9.5.89,
  author =	{Boros, Endre and Kimelfeld, Benny and Pichler, Reinhard and Schweikardt, Nicole},
  title =	{{Enumeration in Data Management (Dagstuhl Seminar 19211)}},
  pages =	{89--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{5},
  editor =	{Boros, Endre and Kimelfeld, Benny and Pichler, Reinhard and Schweikardt, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.5.89},
  URN =		{urn:nbn:de:0030-drops-113822},
  doi =		{10.4230/DagRep.9.5.89},
  annote =	{Keywords: constant delay, databases, dynamic complexity, enumeration, polynomial delay, query evaluation}
}

Document

DOI: 10.4230/LIPIcs.STACS.2015.103

Markov Decision Processes and Stochastic Games with Total Effective Payoff

Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We consider finite Markov decision processes (MDPs) with undiscounted total effective payoff. We show that there exist uniformly optimal pure stationary strategies that can be computed by solving a polynomial number of linear programs. We apply this result to two-player zero-sum stochastic games with perfect information and undiscounted total effective payoff, and derive the existence of a saddle point in uniformly optimal pure stationary strategies.

Cite as

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Markov Decision Processes and Stochastic Games with Total Effective Payoff. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 103-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boros_et_al:LIPIcs.STACS.2015.103,
  author =	{Boros, Endre and Elbassioni, Khaled and Gurvich, Vladimir and Makino, Kazuhisa},
  title =	{{Markov Decision Processes and Stochastic Games with Total Effective Payoff}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{103--115},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.103},
  URN =		{urn:nbn:de:0030-drops-49074},
  doi =		{10.4230/LIPIcs.STACS.2015.103},
  annote =	{Keywords: Markov decision processes, undiscounted stochastic games, linear programming, mean payoff, total payoff}
}

Search Results

Documents authored by Boros, Endre

Enumeration in Data Management (Dagstuhl Seminar 19211)

Abstract

Cite as

Markov Decision Processes and Stochastic Games with Total Effective Payoff

Abstract

Cite as

Thanks for your feedback!

Could not send message