6 Search Results for "Sch�ller, Marcus"


Document
Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482)

Authors: Holger Dell, Mark R. Jerrum, Haiko Müller, Konrad Anand, and Marcus Pappik

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


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22482 "Counting and Sampling: Algorithms and Complexity". We document the talks presented, covering many advances in the area made over the last five years. As well, we document the progress made by working groups on future projects.

Cite as

Holger Dell, Mark R. Jerrum, Haiko Müller, Konrad Anand, and Marcus Pappik. Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482). In Dagstuhl Reports, Volume 12, Issue 11, pp. 124-145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{dell_et_al:DagRep.12.11.124,
  author =	{Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus},
  title =	{{Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482)}},
  pages =	{124--145},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.124},
  URN =		{urn:nbn:de:0030-drops-178394},
  doi =		{10.4230/DagRep.12.11.124},
  annote =	{Keywords: Sampling, Counting, Algorithms, Complexity, Statistical Physics, Phase Transitions, Markov Chains, Graphs, Point Processes}
}
Document
Offloading Safety- and Mission-Critical Tasks via Unreliable Connections

Authors: Lea Schönberger, Georg von der Brüggen, Kuan-Hsun Chen, Benjamin Sliwa, Hazem Youssef, Aswin Karthik Ramachandran Venkatapathy, Christian Wietfeld, Michael ten Hompel, and Jian-Jia Chen

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)


Abstract
For many cyber-physical systems, e.g., IoT systems and autonomous vehicles, offloading workload to auxiliary processing units has become crucial. However, since this approach highly depends on network connectivity and responsiveness, typically only non-critical tasks are offloaded, which have less strict timing requirements than critical tasks. In this work, we provide two protocols allowing to offload critical and non-critical tasks likewise, while providing different service levels for non-critical tasks in the event of an unsuccessful offloading operation, depending on the respective system requirements. We analyze the worst-case timing behavior of the local cyber-physical system and, based on these analyses, we provide a sufficient schedulability test for each of the proposed protocols. In the course of comprehensive experiments, we show that our protocols have reasonable acceptance ratios under the provided schedulability tests. Moreover, we demonstrate that the system behavior under our proposed protocols is strongly dependent on probability of unsuccessful offloading operations, the percentage of critical tasks in the system, and the amount of offloaded workload.

Cite as

Lea Schönberger, Georg von der Brüggen, Kuan-Hsun Chen, Benjamin Sliwa, Hazem Youssef, Aswin Karthik Ramachandran Venkatapathy, Christian Wietfeld, Michael ten Hompel, and Jian-Jia Chen. Offloading Safety- and Mission-Critical Tasks via Unreliable Connections. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{schonberger_et_al:LIPIcs.ECRTS.2020.18,
  author =	{Sch\"{o}nberger, Lea and von der Br\"{u}ggen, Georg and Chen, Kuan-Hsun and Sliwa, Benjamin and Youssef, Hazem and Ramachandran Venkatapathy, Aswin Karthik and Wietfeld, Christian and ten Hompel, Michael and Chen, Jian-Jia},
  title =	{{Offloading Safety- and Mission-Critical Tasks via Unreliable Connections}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.18},
  URN =		{urn:nbn:de:0030-drops-123811},
  doi =		{10.4230/LIPIcs.ECRTS.2020.18},
  annote =	{Keywords: internet of things, cyber-physical systems, real-time, mixed-criticality, self-suspension, computation offloading, scheduling, communication}
}
Document
Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151)

Authors: David Hutchison, Klara Nahrstedt, Marcus Schöller, Indra Spiecker gen. Döhmann, and Markus Tauber

Published in: Dagstuhl Reports, Volume 5, Issue 4 (2015)


Abstract
Dagstuhl Seminar 15151 entitled “Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations” brought together researchers from different disciplines in order to establish a research agenda for making future services in our increasingly connected world more resilient and secure, as well as addressing privacy. The participants came from a range of disciplines covering the techno-legal domain, resilience and systems security, and socio-technical concerns. The use case domains that were discussed during the Seminar covered the Internet of Things (IoT) as well as Cloud-based applications in which flexible service composition is a crucial element. From a starting point covering the “big picture”, the legal viewpoint, the technical viewpoint, and the organisational viewpoint, we derived initial research questions in small groups, and the questions and issues arising were then consolidated and refined. The groups discussed the issues in depth and have produced the report and the research agenda contained here.

Cite as

David Hutchison, Klara Nahrstedt, Marcus Schöller, Indra Spiecker gen. Döhmann, and Markus Tauber. Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151). In Dagstuhl Reports, Volume 5, Issue 4, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{hutchison_et_al:DagRep.5.4.1,
  author =	{Hutchison, David and Nahrstedt, Klara and Sch\"{o}ller, Marcus and Spiecker gen. D\"{o}hmann, Indra and Tauber, Markus},
  title =	{{Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151)}},
  pages =	{1--17},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{4},
  editor =	{Hutchison, David and Nahrstedt, Klara and Sch\"{o}ller, Marcus and Spiecker gen. D\"{o}hmann, Indra and Tauber, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.4.1},
  URN =		{urn:nbn:de:0030-drops-52725},
  doi =		{10.4230/DagRep.5.4.1},
  annote =	{Keywords: Resilience, security, privacy, legal aspects, networked systems, organisations, society}
}
Document
Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players

Authors: Tomas Jelinek, Marcus Klaas, and Guido Schäfer

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)


Abstract
The problem of computing optimal network tolls that induce a Nash equilibrium of minimum total cost has been studied intensively in the literature, but mostly under the assumption that these tolls are unrestricted. Here we consider this problem under the more realistic assumption that the tolls have to respect some given upper bound restrictions on the arcs. The problem of taxing subnetworks optimally constitutes an important special case of this problem. We study the restricted network toll problem for both non-atomic and atomic (unweighted and weighted) players; our studies are the first that also incorporate heterogeneous players, i.e., players with different sensitivities to tolls. For non-atomic and heterogeneous players, we prove that the problem is NP-hard even for single-commodity networks and affine latency functions. We therefore focus on parallel-arc networks and give an algorithm for optimally taxing subnetworks with affine latency functions. For weighted atomic players, the problem is NP-hard already for parallel-arc networks and linear latency functions, even if players are homogeneous. In contrast, for unweighted atomic and homogeneous players, we develop an algorithm to compute optimal restricted tolls for parallel-arc networks and arbitrary (standard) latency functions. Similarly, for unweighted atomic and heterogeneous players, we derive an algorithm for optimally taxing subnetworks for parallel-arc networks and arbitrary (standard) latency functions. The key to most of our results is to derive (combinatorial) characterizations of flows that are inducible by restricted tolls. These characterizations might be of independent interest.

Cite as

Tomas Jelinek, Marcus Klaas, and Guido Schäfer. Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 433-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{jelinek_et_al:LIPIcs.STACS.2014.433,
  author =	{Jelinek, Tomas and Klaas, Marcus and Sch\"{a}fer, Guido},
  title =	{{Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.433},
  URN =		{urn:nbn:de:0030-drops-44771},
  doi =		{10.4230/LIPIcs.STACS.2014.433},
  annote =	{Keywords: Network routing games, coordination mechanisms, network tolls, taxing subnetworks, heterogeneous players}
}
Document
Alignment-free sequence comparison with spaced k-mers

Authors: Marcus Boden, Martin Schöneich, Sebastian Horwege, Sebastian Lindner, Chris Leimeister, and Burkhard Morgenstern

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013


Abstract
Alignment-free methods are increasingly used for genome analysis and phylogeny reconstruction since they circumvent various difficulties of traditional approaches that rely on multiple sequence alignments. In particular, they are much faster than alignment-based methods. Most alignment-free approaches work by analyzing the k-mer composition of sequences. In this paper, we propose to use 'spaced k-mers', i.e. patterns of deterministic and 'don't care' positions instead of contiguous k-mers. Using simulated and real-world sequence data, we demonstrate that this approach produces better phylogenetic trees than alignment-free methods that rely on contiguous k-mers. In addition, distances calculated with spaced k-mers appear to be statistically more stable than distances based on contiguous k-mers.

Cite as

Marcus Boden, Martin Schöneich, Sebastian Horwege, Sebastian Lindner, Chris Leimeister, and Burkhard Morgenstern. Alignment-free sequence comparison with spaced k-mers. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 24-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{boden_et_al:OASIcs.GCB.2013.24,
  author =	{Boden, Marcus and Sch\"{o}neich, Martin and Horwege, Sebastian and Lindner, Sebastian and Leimeister, Chris and Morgenstern, Burkhard},
  title =	{{Alignment-free sequence comparison with spaced k-mers}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{24--34},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.24},
  URN =		{urn:nbn:de:0030-drops-42334},
  doi =		{10.4230/OASIcs.GCB.2013.24},
  annote =	{Keywords: Alignment-free sequence comparison, phylogeny reconstruction}
}
Document
On the Smoothed Price of Anarchy of the Traffic Assignment Problem

Authors: Luciana Buriol, Marcus Ritt, Felix Rodrigues, and Guido Schäfer

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)


Abstract
We study the effect of perturbations on the Price of Anarchy for the Traffic Assignment Problem. Adopting the smoothed analysis approach, we randomly perturb the latency functions of the given network and estimate the expected Price of Anarchy on the perturbed instances. We provide both theoretical and experimental results that show that the Smoothed Price of Anarchy is of the same order of magnitude as the original one.

Cite as

Luciana Buriol, Marcus Ritt, Felix Rodrigues, and Guido Schäfer. On the Smoothed Price of Anarchy of the Traffic Assignment Problem. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 122-133, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{buriol_et_al:OASIcs.ATMOS.2011.122,
  author =	{Buriol, Luciana and Ritt, Marcus and Rodrigues, Felix and Sch\"{a}fer, Guido},
  title =	{{On the Smoothed Price of Anarchy of the Traffic Assignment Problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{122--133},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.122},
  URN =		{urn:nbn:de:0030-drops-32727},
  doi =		{10.4230/OASIcs.ATMOS.2011.122},
  annote =	{Keywords: Traffic Assignment Problem, Smoothed Analysis, Price of Anarchy}
}
  • Refine by Author
  • 2 Schäfer, Guido
  • 1 Anand, Konrad
  • 1 Boden, Marcus
  • 1 Buriol, Luciana
  • 1 Chen, Jian-Jia
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Mathematical analysis
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 1 Algorithms
  • 1 Alignment-free sequence comparison
  • 1 Complexity
  • 1 Counting
  • 1 Graphs
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2011
  • 1 2013
  • 1 2014
  • 1 2015
  • 1 2020
  • 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