6 Search Results for "Rasmussen, Peter M. R."


Document
Track A: Algorithms, Complexity and Games
Optimal Decremental Connectivity in Non-Sparse Graphs

Authors: Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in O(m + n poly log n) total time. Interspersed with the deletions, it can answer queries whether any two given vertices currently belong to the same (2-edge-)connected component in constant time. Our result is based on a general Monte-Carlo randomized reduction from decremental c-edge-connectivity to a variant of fully-dynamic c-edge-connectivity on a sparse graph. For non-sparse graphs with Ω(n poly log n) edges, our connectivity and 2-edge-connectivity algorithms handle all deletions in optimal linear total time, using existing algorithms for the respective fully-dynamic problems. This improves upon an O(m log (n² / m) + n poly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n²) edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an Ω(log n/log log n) worst-case time lower bound in the decremental setting [Alstrup, Husfeldt, and Rauhe FOCS'98] as well as an Ω(log n) amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC'04].

Cite as

Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.ICALP.2023.6,
  author =	{Aamand, Anders and Karczmarz, Adam and {\L}\k{a}cki, Jakub and Parotsidis, Nikos and Rasmussen, Peter M. R. and Thorup, Mikkel},
  title =	{{Optimal Decremental Connectivity in Non-Sparse Graphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.6},
  URN =		{urn:nbn:de:0030-drops-180581},
  doi =		{10.4230/LIPIcs.ICALP.2023.6},
  annote =	{Keywords: decremental connectivity, dynamic connectivity}
}
Document
Machine Learning for Science: Bridging Data-Driven and Mechanistic Modelling (Dagstuhl Seminar 22382)

Authors: Philipp Berens, Kyle Cranmer, Neil D. Lawrence, Ulrike von Luxburg, and Jessica Montgomery

Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)


Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 22382 "Machine Learning for Science: Bridging Data-Driven and Mechanistic Modelling". Today’s scientific challenges are characterised by complexity. Interconnected natural, technological, and human systems are influenced by forces acting across time- and spatial-scales, resulting in complex interactions and emergent behaviours. Understanding these phenomena - and leveraging scientific advances to deliver innovative solutions to improve society’s health, wealth, and well-being - requires new ways of analysing complex systems. The transformative potential of AI stems from its widespread applicability across disciplines, and will only be achieved through integration across research domains. AI for science is a rendezvous point. It brings together expertise from AI and application domains; combines modelling knowledge with engineering know-how; and relies on collaboration across disciplines and between humans and machines. Alongside technical advances, the next wave of progress in the field will come from building a community of machine learning researchers, domain experts, citizen scientists, and engineers working together to design and deploy effective AI tools. This report summarises the discussions from the seminar and provides a roadmap to suggest how different communities can collaborate to deliver a new wave of progress in AI and its application for scientific discovery.

Cite as

Philipp Berens, Kyle Cranmer, Neil D. Lawrence, Ulrike von Luxburg, and Jessica Montgomery. Machine Learning for Science: Bridging Data-Driven and Mechanistic Modelling (Dagstuhl Seminar 22382). In Dagstuhl Reports, Volume 12, Issue 9, pp. 150-199, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{berens_et_al:DagRep.12.9.150,
  author =	{Berens, Philipp and Cranmer, Kyle and Lawrence, Neil D. and von Luxburg, Ulrike and Montgomery, Jessica},
  title =	{{Machine Learning for Science: Bridging Data-Driven and Mechanistic Modelling (Dagstuhl Seminar 22382)}},
  pages =	{150--199},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{9},
  editor =	{Berens, Philipp and Cranmer, Kyle and Lawrence, Neil D. and von Luxburg, Ulrike and Montgomery, Jessica},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.9.150},
  URN =		{urn:nbn:de:0030-drops-178125},
  doi =		{10.4230/DagRep.12.9.150},
  annote =	{Keywords: machine learning, artificial intelligence, life sciences, physical sciences, environmental sciences, simulation, causality, modelling}
}
Document
Tiling with Squares and Packing Dominos in Polynomial Time

Authors: Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
A polyomino is a polygonal region with axis-parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container P. We give polynomial-time algorithms for deciding if P can be tiled with k× k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k× k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2× 1 dominos, allowing rotations by 90^∘. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2× 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2× 2 squares is known to be NP-hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P. However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(nlog n)-time algorithm for tiling with squares, where n is the number of corners of P. We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O(n³) vertices. This leads to algorithms with running times O(n³(log³ n)/(log²log n)) and O(n³(log² n)/(log log n)), respectively.

Cite as

Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen. Tiling with Squares and Packing Dominos in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 1:1-1:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2022.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Ahle, Thomas and Rasmussen, Peter M. R.},
  title =	{{Tiling with Squares and Packing Dominos in Polynomial Time}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.1},
  URN =		{urn:nbn:de:0030-drops-160096},
  doi =		{10.4230/LIPIcs.SoCG.2022.1},
  annote =	{Keywords: packing, tiling, polyominos}
}
Document
Vision Paper
Modeling and Representing Real-World Spatio-Temporal Data in Databases (Vision Paper)

Authors: José Moreira, José Duarte, and Paulo Dias

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)


Abstract
Research in general-purpose spatio-temporal databases has focused mainly on the development of data models and query languages. However, since spatio-temporal data are captured as snapshots, an important research question is how to compute and represent the spatial evolution of the data between observations in databases. Current methods impose constraints to ensure data integrity, but, in some cases, these constraints do not allow the methods to obtain a natural representation of the evolution of spatio-temporal phenomena over time. This paper discusses a different approach where morphing techniques are used to represent the evolution of spatio-temporal data in databases. First, the methods proposed in the spatio-temporal databases literature are presented and their main limitations are discussed with the help of illustrative examples. Then, the paper discusses the use of morphing techniques to handle spatio-temporal data, and the requirements and the challenges that must be investigated to allow the use of these techniques in databases. Finally, a set of examples is presented to compare the approaches investigated in this work. The need for benchmarking methodologies for spatio-temporal databases is also highlighted.

Cite as

José Moreira, José Duarte, and Paulo Dias. Modeling and Representing Real-World Spatio-Temporal Data in Databases (Vision Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{moreira_et_al:LIPIcs.COSIT.2019.6,
  author =	{Moreira, Jos\'{e} and Duarte, Jos\'{e} and Dias, Paulo},
  title =	{{Modeling and Representing Real-World Spatio-Temporal Data in Databases}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.6},
  URN =		{urn:nbn:de:0030-drops-110984},
  doi =		{10.4230/LIPIcs.COSIT.2019.6},
  annote =	{Keywords: spatio-temporal databases, region interpolation problem, moving regions, morphing techniques}
}
Document
Timed Basic Parallel Processes

Authors: Lorenzo Clemente, Piotr Hofman, and Patrick Totzke

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)


Abstract
Timed basic parallel processes (TBPP) extend communication-free Petri nets (aka. BPP or commutative context-free grammars) by a global notion of time. TBPP can be seen as an extension of timed automata (TA) with context-free branching rules, and as such may be used to model networks of independent timed automata with process creation. We show that the coverability and reachability problems (with unary encoded target multiplicities) are PSPACE-complete and EXPTIME-complete, respectively. For the special case of 1-clock TBPP, both are NP-complete and hence not more complex than for untimed BPP. This contrasts with known super-Ackermannian-completeness and undecidability results for general timed Petri nets. As a result of independent interest, and basis for our NP upper bounds, we show that the reachability relation of 1-clock TA can be expressed by a formula of polynomial size in the existential fragment of linear arithmetic, which improves on recent results from the literature.

Cite as

Lorenzo Clemente, Piotr Hofman, and Patrick Totzke. Timed Basic Parallel Processes. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.CONCUR.2019.15,
  author =	{Clemente, Lorenzo and Hofman, Piotr and Totzke, Patrick},
  title =	{{Timed Basic Parallel Processes}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.15},
  URN =		{urn:nbn:de:0030-drops-109171},
  doi =		{10.4230/LIPIcs.CONCUR.2019.15},
  annote =	{Keywords: Timed Automata, Petri Nets}
}
Document
Simple Priced Timed Games are not That Simple

Authors: Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary (positive and negative) weights and show that, for an important subclass of theirs (the so-called simple priced timed games), one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games (with arbitrary weights and one-clock).

Cite as

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege. Simple Priced Timed Games are not That Simple. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 278-292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{brihaye_et_al:LIPIcs.FSTTCS.2015.278,
  author =	{Brihaye, Thomas and Geeraerts, Gilles and Haddad, Axel and Lefaucheux, Engel and Monmege, Benjamin},
  title =	{{Simple Priced Timed Games are not That Simple}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{278--292},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.278},
  URN =		{urn:nbn:de:0030-drops-56235},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.278},
  annote =	{Keywords: Priced timed games, real-time systems, game theory}
}
  • Refine by Author
  • 2 Aamand, Anders
  • 2 Rasmussen, Peter M. R.
  • 1 Abrahamsen, Mikkel
  • 1 Ahle, Thomas
  • 1 Berens, Philipp
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Shape modeling
  • 1 Information systems → Data model extensions
  • 1 Information systems → Spatial-temporal systems
  • Show More...

  • Refine by Keyword
  • 1 Petri Nets
  • 1 Priced timed games
  • 1 Timed Automata
  • 1 artificial intelligence
  • 1 causality
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2019
  • 2 2023
  • 1 2015
  • 1 2022

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