98 Search Results for "Katoen, Joost-Pieter"


Volume

LIPIcs, Volume 138

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

MFCS 2019, August 26-30, 2019, Aachen, Germany

Editors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen

Document
Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241)

Authors: Sebastian Junges, Joost-Pieter Katoen, Scott Sanner, Guy Van den Broeck, and Bahare Salmani

Published in: Dagstuhl Reports, Volume 13, Issue 6 (2024)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23241 "Scalable Analysis of Probabilistic Models and Programs". The seminar brought together researchers from probabilistic graphical models, verification of probabilistic programming languages, and probabilistic planning. The communities bring vastly different perspectives on the methods and goals of inference under uncertainty. In this seminar, we worked towards a common understanding of how the different angles yield subtle differences in the problem statements and how the different methods provide different strengths and weaknesses. The report describes the different areas, the activities during the seminar including hot topics that were vividly discussed, and an overview of the technical talks.

Cite as

Sebastian Junges, Joost-Pieter Katoen, Scott Sanner, Guy Van den Broeck, and Bahare Salmani. Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241). In Dagstuhl Reports, Volume 13, Issue 6, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{junges_et_al:DagRep.13.6.1,
  author =	{Junges, Sebastian and Katoen, Joost-Pieter and Sanner, Scott and Van den Broeck, Guy and Salmani, Bahare},
  title =	{{Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241)}},
  pages =	{1--21},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{6},
  editor =	{Junges, Sebastian and Katoen, Joost-Pieter and Sanner, Scott and Van den Broeck, Guy and Salmani, Bahare},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.6.1},
  URN =		{urn:nbn:de:0030-drops-196362},
  doi =		{10.4230/DagRep.13.6.1},
  annote =	{Keywords: model counting, probabilistic inference, probabilistic model checking, probabilistic planning, probabilistic programs}
}
Document
Towards Concurrent Quantitative Separation Logic

Authors: Ira Fesefeldt, Joost-Pieter Katoen, and Thomas Noll

Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)


Abstract
In this paper, we develop a novel verification technique to reason about programs featuring concurrency, pointers and randomization. While the integration of concurrency and pointers is well studied, little is known about the combination of all three paradigms. To close this gap, we combine two kinds of separation logic - Quantitative Separation Logic and Concurrent Separation Logic - into a new separation logic that enables reasoning about lower bounds of the probability to realise a postcondition by executing such a program.

Cite as

Ira Fesefeldt, Joost-Pieter Katoen, and Thomas Noll. Towards Concurrent Quantitative Separation Logic. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fesefeldt_et_al:LIPIcs.CONCUR.2022.25,
  author =	{Fesefeldt, Ira and Katoen, Joost-Pieter and Noll, Thomas},
  title =	{{Towards Concurrent Quantitative Separation Logic}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{25:1--25:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.25},
  URN =		{urn:nbn:de:0030-drops-170881},
  doi =		{10.4230/LIPIcs.CONCUR.2022.25},
  annote =	{Keywords: Randomization, Pointers, Heap-Manipulating, Separation Logic, Concurrency}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
On Decidability of Time-Bounded Reachability in CTMDPs

Authors: Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We consider the time-bounded reachability problem for continuous-time Markov decision processes. We show that the problem is decidable subject to Schanuel’s conjecture. Our decision procedure relies on the structure of optimal policies and the conditional decidability (under Schanuel’s conjecture) of the theory of reals extended with exponential and trigonometric functions over bounded domains. We further show that any unconditional decidability result would imply unconditional decidability of the bounded continuous Skolem problem, or equivalently, the problem of checking if an exponential polynomial has a non-tangential zero in a bounded interval. We note that the latter problems are also decidable subject to Schanuel’s conjecture but finding unconditional decision procedures remain longstanding open problems.

Cite as

Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani. On Decidability of Time-Bounded Reachability in CTMDPs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 133:1-133:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{majumdar_et_al:LIPIcs.ICALP.2020.133,
  author =	{Majumdar, Rupak and Salamati, Mahmoud and Soudjani, Sadegh},
  title =	{{On Decidability of Time-Bounded Reachability in CTMDPs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{133:1--133:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.133},
  URN =		{urn:nbn:de:0030-drops-125408},
  doi =		{10.4230/LIPIcs.ICALP.2020.133},
  annote =	{Keywords: CTMDP, Time bounded reachability, Continuous Skolem Problem, Schanuel’s Conjecture}
}
Document
Complete Volume
LIPIcs, Volume 138, MFCS'19, Complete Volume

Authors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
LIPIcs, Volume 138, MFCS'19, Complete Volume

Cite as

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Proceedings{rossmanith_et_al:LIPIcs.MFCS.2019,
  title =	{{LIPIcs, Volume 138, MFCS'19, Complete Volume}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019},
  URN =		{urn:nbn:de:0030-drops-112092},
  doi =		{10.4230/LIPIcs.MFCS.2019},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{rossmanith_et_al:LIPIcs.MFCS.2019.0,
  author =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.0},
  URN =		{urn:nbn:de:0030-drops-109444},
  doi =		{10.4230/LIPIcs.MFCS.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Trustworthy Graph Algorithms (Invited Talk)

Authors: Mohammad Abdulaziz, Kurt Mehlhorn, and Tobias Nipkow

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching.

Cite as

Mohammad Abdulaziz, Kurt Mehlhorn, and Tobias Nipkow. Trustworthy Graph Algorithms (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{abdulaziz_et_al:LIPIcs.MFCS.2019.1,
  author =	{Abdulaziz, Mohammad and Mehlhorn, Kurt and Nipkow, Tobias},
  title =	{{Trustworthy Graph Algorithms}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.1},
  URN =		{urn:nbn:de:0030-drops-109456},
  doi =		{10.4230/LIPIcs.MFCS.2019.1},
  annote =	{Keywords: graph algorithms, formal correct proofs, Isabelle, LEDA, certifying algorithms}
}
Document
Invited Talk
Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time (Invited Talk)

Authors: Alexandra Silva

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Guarded Kleene Algebra with Tests (GKAT) is a variation on Kleene Algebra with Tests (KAT) that arises by restricting the union (+) and iteration (*) operations from KAT to predicate-guarded versions. We develop the (co)algebraic theory of GKAT and show how it can be efficiently used to reason about imperative programs. In contrast to KAT, whose equational theory is PSPACE-complete, we show that the equational theory of GKAT is (almost) linear time. We also provide a full Kleene theorem and prove completeness for an analogue of Salomaa’s axiomatization of Kleene Algebra. We will also discuss how this result has practical implications in the verification of programs, with examples from network and probabilistic programming. This is joint work with Nate Foster, Justin Hsu, Tobias Kappe, Dexter Kozen, and Steffen Smolka.

Cite as

Alexandra Silva. Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{silva:LIPIcs.MFCS.2019.2,
  author =	{Silva, Alexandra},
  title =	{{Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.2},
  URN =		{urn:nbn:de:0030-drops-109462},
  doi =		{10.4230/LIPIcs.MFCS.2019.2},
  annote =	{Keywords: Kleene algebra, verification, decision procedures}
}
Document
Invited Talk
Picking Random Vertices (Invited Talk)

Authors: Daniel Lokshtanov

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that is based on picking a vertex at random and declaring it to not be part of the solution.

Cite as

Daniel Lokshtanov. Picking Random Vertices (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{lokshtanov:LIPIcs.MFCS.2019.3,
  author =	{Lokshtanov, Daniel},
  title =	{{Picking Random Vertices}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.3},
  URN =		{urn:nbn:de:0030-drops-109478},
  doi =		{10.4230/LIPIcs.MFCS.2019.3},
  annote =	{Keywords: Graph Algorithm}
}
Document
Invited Talk
Popular Matchings: Good, Bad, and Mixed (Invited Talk)

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We consider the landscape of popular matchings in a bipartite graph G where every vertex has strict preferences over its neighbors. This is a very well-studied model in two-sided matching markets. A matching M is popular if it does not lose a head-to-head election against any matching, where each vertex casts a vote for the matching where it gets a better assignment. Roughly speaking, a popular matching is one such that there is no matching where more vertices are happier. The notion of popularity is more relaxed than stability: a classical notion studied for the last several decades. Popular matchings always exist in G since stable matchings always exist in a bipartite graph and every stable matching is popular. Algorithmically speaking, the landscape of popular matching seems to have only a few bright spots. Every stable matching is a min-size popular matching and there are also simple linear time algorithms for computing a max-size popular matching and for the popular edge problem. All these algorithms reduce the popular matching problem to an appropriate question in stable matchings and solve the corresponding stable matching problem. We now know NP-hardness results for many popular matching problems. These include the min-cost/max-weight popular matching problem and the problem of deciding if G admits a popular matching that is neither a min-size nor a max-size popular matching. For non-bipartite graphs, it is NP-hard to even decide if a popular matching exists or not. A mixed matching is a probability distribution or a lottery over matchings. A popular mixed matching is one that never loses a head-to-head election against any mixed matching. As an allocation mechanism, a popular mixed matching has several nice properties. Moreover, finding a max-weight or min-cost popular mixed matching in G is easy (by solving a linear program). Interestingly, there is always an optimal popular mixed matching Pi with a simple structure: Pi = {(M_0,1/2),(M_1,1/2)} where M_0 and M_1 are matchings in G. Popular mixed matchings always exist in non-bipartite graphs as well and can be computed in polynomial time.

Cite as

Telikepalli Kavitha. Popular Matchings: Good, Bad, and Mixed (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.MFCS.2019.4,
  author =	{Kavitha, Telikepalli},
  title =	{{Popular Matchings: Good, Bad, and Mixed}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.4},
  URN =		{urn:nbn:de:0030-drops-109489},
  doi =		{10.4230/LIPIcs.MFCS.2019.4},
  annote =	{Keywords: Matchings under preferences, Algorithms, NP-Hardness}
}
Document
Invited Talk
Petri Net Reachability Problem (Invited Talk)

Authors: Jérôme Leroux

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of verification. In this presentation, we overview decidability and complexity results over the last fifty years about the Petri net reachability problem.

Cite as

Jérôme Leroux. Petri Net Reachability Problem (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{leroux:LIPIcs.MFCS.2019.5,
  author =	{Leroux, J\'{e}r\^{o}me},
  title =	{{Petri Net Reachability Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{5:1--5:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.5},
  URN =		{urn:nbn:de:0030-drops-109493},
  doi =		{10.4230/LIPIcs.MFCS.2019.5},
  annote =	{Keywords: Petri net, Reachability problem, Formal verification, Concurrency}
}
Document
An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

Authors: Marcin Bienkowski and Hsiang-Hsuan Liu

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
In the online variant of the traveling repairperson problem (TRP), requests arrive in time at points of a metric space X and must be eventually visited by a server. The server starts at a designated point of X and travels at most at unit speed. Each request has a given weight and once the server visits its position, the request is considered serviced; we call such time completion time of the request. The goal is to minimize the weighted sum of completion times of all requests. In this paper, we give a 5.429-competitive deterministic algorithm for line metrics improving over 5.829-competitive solution by Krumke et al. (TCS 2003). Our result is obtained by modifying the schedule by serving requests that are close to the origin first. To compute the competitive ratio of our approach, we use a charging scheme, and later evaluate its properties using a factor-revealing linear program which upper-bounds the competitive ratio.

Cite as

Marcin Bienkowski and Hsiang-Hsuan Liu. An Improved Online Algorithm for the Traveling Repairperson Problem on a Line. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.6,
  author =	{Bienkowski, Marcin and Liu, Hsiang-Hsuan},
  title =	{{An Improved Online Algorithm for the Traveling Repairperson Problem on a Line}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.6},
  URN =		{urn:nbn:de:0030-drops-109503},
  doi =		{10.4230/LIPIcs.MFCS.2019.6},
  annote =	{Keywords: traveling repairperson problem, competitive analysis, minimizing completion time, factor-revealing LP}
}
Document
Query-Competitive Sorting with Uncertainty

Authors: Magnús M. Halldórsson and Murilo Santos de Lima

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query-competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields: (i) a 3/2-query-competitive randomized algorithm; (ii) a 5/3-query-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k; (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also show that the advice complexity of the adaptive problem is floor[n/2] if no error threshold is allowed, and ceil[n/3 * lg 3] for the general case.

Cite as

Magnús M. Halldórsson and Murilo Santos de Lima. Query-Competitive Sorting with Uncertainty. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.MFCS.2019.7,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and de Lima, Murilo Santos},
  title =	{{Query-Competitive Sorting with Uncertainty}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.7},
  URN =		{urn:nbn:de:0030-drops-109519},
  doi =		{10.4230/LIPIcs.MFCS.2019.7},
  annote =	{Keywords: online algorithms, sorting, randomized algorithms, advice complexity, threshold tolerance graphs}
}
Document
Better Bounds for Online Line Chasing

Authors: Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, ..., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1 , ..., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1.412 for convex body chasing in 2 dimensions.

Cite as

Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias. Better Bounds for Online Line Chasing. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.8,
  author =	{Bienkowski, Marcin and Byrka, Jaros{\l}aw and Chrobak, Marek and Coester, Christian and Je\.{z}, {\L}ukasz and Koutsoupias, Elias},
  title =	{{Better Bounds for Online Line Chasing}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-109521},
  doi =		{10.4230/LIPIcs.MFCS.2019.8},
  annote =	{Keywords: convex body chasing, line chasing, competitive analysis}
}
Document
Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

Authors: Patricia Bouyer and Nathan Thomasset

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We study pure Nash equilibria in infinite-duration games on graphs, with partial visibility of actions but communication (based on a graph) among the players. We show that a simple communication mechanism consisting in reporting the deviator when seeing it and propagating this information is sufficient for characterizing Nash equilibria. We propose an epistemic game construction, which conveniently records important information about the knowledge of the players. With this abstraction, we are able to characterize Nash equilibria which follow the simple communication pattern via winning strategies. We finally discuss the size of the construction, which would allow efficient algorithmic solutions to compute Nash equilibria in the original game.

Cite as

Patricia Bouyer and Nathan Thomasset. Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.MFCS.2019.9,
  author =	{Bouyer, Patricia and Thomasset, Nathan},
  title =	{{Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.9},
  URN =		{urn:nbn:de:0030-drops-109532},
  doi =		{10.4230/LIPIcs.MFCS.2019.9},
  annote =	{Keywords: Multiplayer games, Nash equilibria, partial information}
}
  • Refine by Author
  • 11 Katoen, Joost-Pieter
  • 2 Bell, Paul C.
  • 2 Bienkowski, Marcin
  • 2 Bulatov, Andrei A.
  • 2 Haverkort, Boudewijn
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Problems, reductions and completeness
  • 7 Mathematics of computing → Graph algorithms
  • 7 Mathematics of computing → Graph theory
  • 7 Theory of computation → Design and analysis of algorithms
  • 6 Theory of computation
  • Show More...

  • Refine by Keyword
  • 4 verification
  • 3 Concurrency
  • 3 Formal verification
  • 3 decidability
  • 3 first-order logic
  • Show More...

  • Refine by Type
  • 97 document
  • 1 volume

  • Refine by Publication Year
  • 87 2019
  • 4 2007
  • 1 2011
  • 1 2013
  • 1 2015
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail