4 Search Results for "Schneider, Stefan"

Document
DOI: 10.4230/LIPIcs.SEA.2022.4
Fast Succinct Retrieval and Approximate Membership Using Ribbon

Authors: Peter C. Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
A retrieval data structure for a static function f: S → {0,1}^r supports queries that return f(x) for any x ∈ S. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ), i.e., a Bloom filter alternative, with false positive rate 2^{-r}. The information-theoretic lower bound for both tasks is r|S| bits. While succinct theoretical constructions using (1+o(1))r|S| bits were known, these could not achieve very small overheads in practice because they have an unfavorable space-time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below 1% while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead ≥ 44%). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We additionally describe homogeneous ribbon filter AMQs, which are even simpler and faster at the price of slightly larger space overhead.
Cite as

Peter C. Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, and Stefan Walzer. Fast Succinct Retrieval and Approximate Membership Using Ribbon. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dillinger_et_al:LIPIcs.SEA.2022.4,
  author =	{Dillinger, Peter C. and H\"{u}bschle-Schneider, Lorenz and Sanders, Peter and Walzer, Stefan},
  title =	{{Fast Succinct Retrieval and Approximate Membership Using Ribbon}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.4},
  URN =		{urn:nbn:de:0030-drops-165385},
  doi =		{10.4230/LIPIcs.SEA.2022.4},
  annote =	{Keywords: AMQ, Bloom filter, dictionary, linear algebra, randomized algorithm, retrieval data structure, static function data structure, succinct data structure, perfect hashing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.21
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming

Authors: Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
In this paper, we investigate the complexity of one-dimensional dynamic programming, or more specifically, of the Least-Weight Subsequence (LWS) problem: Given a sequence of n data items together with weights for every pair of the items, the task is to determine a subsequence S minimizing the total weight of the pairs adjacent in S. A large number of natural problems can be formulated as LWS problems, yielding obvious O(n^2)-time solutions. In many interesting instances, the O(n^2)-many weights can be succinctly represented. Yet except for near-linear time algorithms for some specific special cases, little is known about when an LWS instantiation admits a subquadratic-time algorithm and when it does not. In particular, no lower bounds for LWS instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the fine-grained complexity of succinct instantiations of the LWS problem: Given an LWS instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS instantiation and the corresponding core problem) of problems: a low-rank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)-convolution. Using these equivalences and known SETH-hardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the (min,+)-convolution-hardness of the knapsack problem. Furthermore, we revisit some of the LWS instantiations which are known to be solvable in near-linear time and explain their easiness in terms of the easiness of the corresponding core problems.
Cite as

Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kunnemann_et_al:LIPIcs.ICALP.2017.21,
  author =	{K\"{u}nnemann, Marvin and Paturi, Ramamohan and Schneider, Stefan},
  title =	{{On the Fine-Grained Complexity of One-Dimensional Dynamic Programming}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian 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.ICALP.2017.21},
  URN =		{urn:nbn:de:0030-drops-74688},
  doi =		{10.4230/LIPIcs.ICALP.2017.21},
  annote =	{Keywords: Least-Weight Subsequence, SETH, Fine-Grained Complexity, Knapsack, Subquadratic Algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.138
Speed-Consumption Tradeoff for Electric Vehicle Route Planning

Authors: Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second---several orders of magnitude faster than the exhaustive algorithm.
Cite as

Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 138-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:OASIcs.ATMOS.2014.138,
  author =	{Baum, Moritz and Dibbelt, Julian and H\"{u}bschle-Schneider, Lorenz and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Speed-Consumption Tradeoff for Electric Vehicle Route Planning}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{138--151},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.138},
  URN =		{urn:nbn:de:0030-drops-47583},
  doi =		{10.4230/OASIcs.ATMOS.2014.138},
  annote =	{Keywords: electric vehicles, shortest paths, route planning, bicriteria optimization, algorithm engineering}
}
Document
DOI: 10.4230/DagSemProc.05402.1
Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland

Authors: Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf

Published in: Dagstuhl Seminar Proceedings, Volume 5402, Perspectives Workshop (2006)

Abstract
Im Rahmen des Dagstuhl Perspektiven Workshop 05402 "Challenges for Software Engineering Research" haben führende Software Engineering Professoren den derzeitigen Stand der Softwaretechnik in Deutschland charakterisiert und Handlungsempfehlungen für Wirtschaft, Forschung und Politik abgeleitet. Das Manifest fasst die diese Empfehlungen und die Bedeutung und Entwicklung des Fachgebiets prägnant zusammen.
Cite as

Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf. Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland. In Perspectives Workshop. Dagstuhl Seminar Proceedings, Volume 5402, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{broy_et_al:DagSemProc.05402.1,
  author =	{Broy, Manfred and Jarke, Matthias and Nagl, Manfred and Rombach, Hans Dieter and Cremers, Armin B. and Ebert, J\"{u}rgen and Glesner, Sabine and Glinz, Martin and Goedicke, Michael and Goos, Gerhard and Gruhn, Volker and Hasselbring, Wilhelm and J\"{a}hnichen, Stefan and Kowalewski, Stefan and Kr\"{a}mer, Bernd J. and Leue, Stefan and Lewerentz, Claus and Liggesmeyer, Peter and L\"{u}th, Christoph and Paech, Barbara and Partsch, Helmut A. and Philippow, Ilka and Prechelt, Lutz and Rausch, Andreas and de Roever, Willem-Paul and Rumpe, Bernhard and R\"{u}nger, Gudula and Sch\"{a}fer, Wilhelm and Schneider, Kurt and Sch\"{u}rr, Andy and Tichy, Walter F. and Westfechtel, Bernhard and Zimmermann, Wolf and Z\"{u}ndorf, Albert},
  title =	{{Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland}},
  booktitle =	{Perspectives Workshop},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5402},
  editor =	{Manfred Broy and Manfred Nagl and Hans Dieter Rombach and Matthias Jarke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05402.1},
  URN =		{urn:nbn:de:0030-drops-5853},
  doi =		{10.4230/DagSemProc.05402.1},
  annote =	{Keywords: Software Engineering, Software Technik, Strategie}
}
  • Refine by Author
  • 2 Hübschle-Schneider, Lorenz
  • 1 Baum, Moritz
  • 1 Broy, Manfred
  • 1 Cremers, Armin B.
  • 1 Dibbelt, Julian
  • Show More...

  • Refine by Classification
  • 1 Information systems → Point lookups
  • 1 Theory of computation → Data compression

  • Refine by Keyword
  • 1 AMQ
  • 1 Bloom filter
  • 1 Fine-Grained Complexity
  • 1 Knapsack
  • 1 Least-Weight Subsequence
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2006
  • 1 2014
  • 1 2017
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact