4 Search Results for "Wolfgang, Paul J."

Document
DOI: 10.4230/LIPIcs.SOCG.2015.156
Spanners and Reachability Oracles for Directed Transmission Graphs

Authors: Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Let P be a set of n points in d dimensions, each with an associated radius r_p > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius r_p around p. Let t > 1. A t-spanner H for G is a sparse subgraph of G such that for any two vertices p, q connected by a path of length l in G, there is a p-q-path of length at most tl in H. We show how to compute a t-spanner for G if d=2. The running time is O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius of two points in P. We extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a first application, we prove a property of the t-spanner that allows us to find a BFS tree in G for any given start vertex s of P in the same time. After that, we deal with reachability oracles for G. These are data structures that answer reachability queries: given two vertices, is there a directed path between them? The quality of a reachability oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, the radius ratio Psi again turns out to be an important measure for the complexity of the problem. We present three different data structures whose quality depends on Psi: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n) and preproccesing time O(n log n); (ii) if Psi >= sqrt(3), we get Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^5 n^(3/2)); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with Q(n) = O(n^(2/3)log n) and S(n) = O(n^(5/3) log n) that answers queries correctly with high probability. We employ our t-spanner to achieve a fast preproccesing time of O(Psi^5 n^(3/2)) and O(n^(5/3) log^2 n) in case (ii) and (iii), respectively.
Cite as

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Spanners and Reachability Oracles for Directed Transmission Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 156-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.SOCG.2015.156,
  author =	{Kaplan, Haim and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul},
  title =	{{Spanners and Reachability Oracles for Directed Transmission Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{156--170},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.156},
  URN =		{urn:nbn:de:0030-drops-51062},
  doi =		{10.4230/LIPIcs.SOCG.2015.156},
  annote =	{Keywords: Transmission Graphs, Reachability Oracles, Spanner, Intersection Graph}
}
Document
DOI: 10.4230/DagSemProc.07462.5
Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy

Authors: Wolfgang L. Zagler, Paul Panek, and Marjo Rauhala

Published in: Dagstuhl Seminar Proceedings, Volume 7462, Assisted Living Systems - Models, Architectures and Engineering Approaches (2008)

Abstract
Installing and using AAL Smart Home-systems in the homes of older people not only offers a tremendous potential for increasing safety and quality of life but may also evoke reluctance and anxiety. Will such a system become a "Big Brother" watching the steps and the behaviour of the inhabitants and betray them to their outside world? In several field-trials of an AAL Smart Home-system with inhabitants of senior residences we were able to learn about the issues concerning acceptance, ethics and privacy when senior citizens and their care persons are confronted with this kind of technology for the first time.
Cite as

Wolfgang L. Zagler, Paul Panek, and Marjo Rauhala. Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy. In Assisted Living Systems - Models, Architectures and Engineering Approaches. Dagstuhl Seminar Proceedings, Volume 7462, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{zagler_et_al:DagSemProc.07462.5,
  author =	{Zagler, Wolfgang L. and Panek, Paul and Rauhala, Marjo},
  title =	{{Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy}},
  booktitle =	{Assisted Living Systems - Models, Architectures and Engineering Approaches},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7462},
  editor =	{Arthur I. Karshmer and J\"{u}rgen Nehmer and Hartmut Raffler and Gerhard Tr\"{o}ster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07462.5},
  URN =		{urn:nbn:de:0030-drops-14549},
  doi =		{10.4230/DagSemProc.07462.5},
  annote =	{Keywords: AAL, Ambient Assisted Living, Smart Homes, field trials, acceptance, ethics, privacy protection, data protection}
}
Document
DOI: 10.4230/DagSemProc.06051.6
Complexity Monotone in Conditions and Future Prediction Errors

Authors: Alexey Chernov, Marcus Hutter, and Jürgen Schmidhuber

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract
We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
Cite as

Alexey Chernov, Marcus Hutter, and Jürgen Schmidhuber. Complexity Monotone in Conditions and Future Prediction Errors. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{chernov_et_al:DagSemProc.06051.6,
  author =	{Chernov, Alexey and Hutter, Marcus and Schmidhuber, J\"{u}rgen},
  title =	{{Complexity Monotone in Conditions and Future Prediction Errors}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.6},
  URN =		{urn:nbn:de:0030-drops-6327},
  doi =		{10.4230/DagSemProc.06051.6},
  annote =	{Keywords: Kolmogorov complexity, posterior bounds, online sequential prediction, Solomonoff prior, monotone conditional complexity, total error, future loss, ra}
}
Document
DOI: 10.4230/DagSemRep.1
Architecture and Performance (Dagstuhl Seminar 9025)

Authors: Wolfgang Gentzsch and Paul J. Wolfgang

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Wolfgang Gentzsch and Paul J. Wolfgang. Architecture and Performance (Dagstuhl Seminar 9025). Dagstuhl Seminar Report 1, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)

Copy BibTex To Clipboard

@TechReport{gentzsch_et_al:DagSemRep.1,
  author =	{Gentzsch, Wolfgang and Wolfgang, Paul J.},
  title =	{{Architecture and Performance (Dagstuhl Seminar 9025)}},
  pages =	{1--12},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{1},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.1},
  URN =		{urn:nbn:de:0030-drops-148898},
  doi =		{10.4230/DagSemRep.1},
}
  • Refine by Author
  • 1 Chernov, Alexey
  • 1 Gentzsch, Wolfgang
  • 1 Hutter, Marcus
  • 1 Kaplan, Haim
  • 1 Mulzer, Wolfgang
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 AAL
  • 1 Ambient Assisted Living
  • 1 Intersection Graph
  • 1 Kolmogorov complexity
  • 1 Reachability Oracles
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 1991
  • 1 2006
  • 1 2008
  • 1 2015

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