4 Search Results for "Westermann, R�diger"

Document
DOI: 10.4230/DagRep.9.4.1
Visual Computing in Materials Sciences (Dagstuhl Seminar 19151)

Authors: Christoph Heinzl, Robert Michael Kirby, Stepan V. Lomov, Guillermo Requena, and Rüdiger Westermann

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
Visual computing has become highly attractive for boosting research endeavors in the materials science domain. Using visual computing, a multitude of different phenomena may now be studied, at various scales, dimensions, or using different modalities. This was simply impossible before. Visual computing techniques generate novel insights to understand, discover, design, and use complex material systems of interest. Its huge potential for retrieving and visualizing (new) information on materials, their characteristics and interrelations as well as on simulating the material's behavior in its target application environment is of core relevance to material scientists. This Dagstuhl seminar on Visual Computing in Materials Sciences thus focuses on the intersection of both domains to guide research endeavors in this field. It targets to provide answers regarding the following four challenges, which are of imminent need: -The Integrated Visual Analysis Challeng identifies standard visualization tools as insufficient for exploring materials science data in detail. What is required are integrated visual analysis tools, which are tailored to a specific application area and guide users in their investigations. Using linked views and other interaction concepts, these tools are required to combine all data domains using meaningful and easy to understand visualization techniques. Especially for the analysis of spatial and temporal data in dynamic processes (e.g., materials tested under load or in different environmental conditions) or multimodal, multiscale data, these tools and techniques are highly anticipated. Only integrated analysis concepts allow to make the most out of all the data available. - The Quantitative Data Visualization Challenge centers around the design and implementation of tailored visual analysis systems for extracting and analyzing derived data (e.g., computed from extracted features over spatial, temporal or even higher dimensional domains). Therefore, feature extraction and quantification techniques, segmentation techniques, or clustering techniques, are required as prerequisites for the targeted visual analysis. As the quantification may easily end up in 25 or more properties to be computed per feature, clustering techniques allow to distinguish features of interest into feature classes. These feature classes may then be statistically evaluated to visualize the properties of the individual features as well as the properties of the different classes. Information visualization techniques will be of special interest for solving this challenge. - The Visual Debugger Challenge is an idea which uses visual analysis to remove errors in the parametrization of a simulation or a data acquisition process. Similarly, to a debugger in computer programming, identifying errors in the code and providing hints to improve, a visual debugger in the domain of visual computing for materials science should show the following characteristics: It should indicate errors and identify wrongly used algorithms in the data analysis. Such a tool should also identify incorrect parameters, which either show no or very limited benefit or even provide erroneous results. Furthermore, it should give directions on how to improve a targeted analysis and suggest suitable algorithms or pipelines for specific tasks. - The Interactive Steering Challenge uses visual analysis tools to control a running simulation or an ongoing data acquisition process. Respective tools monitor costly processes and give directions to improve results regarding the respective targets. For example, in the material analysis domain, this could be a system which provides settings for improved data acquisition based on the current image quality achieved: If the image quality does no more fulfill the target requirements, the system influences all degrees of freedom in the data acquisition to enhance image quality. The same holds for the materials simulation domain. Visual analysis can help to steer target material properties in a specific application environment by predicting tendencies of costly simulation runs, e.g., using cheaper surrogate models.
Cite as

Christoph Heinzl, Robert Michael Kirby, Stepan V. Lomov, Guillermo Requena, and Rüdiger Westermann. Visual Computing in Materials Sciences (Dagstuhl Seminar 19151). In Dagstuhl Reports, Volume 9, Issue 4, pp. 1-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{heinzl_et_al:DagRep.9.4.1,
  author =	{Heinzl, Christoph and Kirby, Robert Michael and Lomov, Stepan V. and Requena, Guillermo and Westermann, R\"{u}diger},
  title =	{{Visual Computing in Materials Sciences (Dagstuhl Seminar 19151)}},
  pages =	{1--42},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Heinzl, Christoph and Kirby, Robert Michael and Lomov, Stepan V. and Requena, Guillermo and Westermann, R\"{u}diger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.4.1},
  URN =		{urn:nbn:de:0030-drops-113024},
  doi =		{10.4230/DagRep.9.4.1},
  annote =	{Keywords: Data Structures, Interaction, Materials Science, Visual Computing, Visualization / Visual Analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.79
Recognizing Planar Laman Graphs

Authors: Jonathan Rollin, Lena Schlipf, and André Schulz

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}). To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.
Cite as

Jonathan Rollin, Lena Schlipf, and André Schulz. Recognizing Planar Laman Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 79:1-79:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rollin_et_al:LIPIcs.ESA.2019.79,
  author =	{Rollin, Jonathan and Schlipf, Lena and Schulz, Andr\'{e}},
  title =	{{Recognizing Planar Laman Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{79:1--79:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.79},
  URN =		{urn:nbn:de:0030-drops-112001},
  doi =		{10.4230/LIPIcs.ESA.2019.79},
  annote =	{Keywords: planar graphs, Laman graphs, network flow, connectivity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.26
Online Makespan Scheduling with Job Migration on Uniform Machines

Authors: Matthias Englert, David Mezlaf, and Matthias Westermann

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to reassign up to k jobs to different machines in the final assignment. For m identical machines, Albers and Hellwig (Algorithmica, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ~~ 1.4659. They show that k = O(m) is sufficient to achieve this bound and no k = o(n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a delta = Theta(1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + delta with k = o(n). We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ~~ 1.7992 with k = O(m). We also show that k = Omega(m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on a subtle imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines.
Cite as

Matthias Englert, David Mezlaf, and Matthias Westermann. Online Makespan Scheduling with Job Migration on Uniform Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{englert_et_al:LIPIcs.ESA.2018.26,
  author =	{Englert, Matthias and Mezlaf, David and Westermann, Matthias},
  title =	{{Online Makespan Scheduling with Job Migration on Uniform Machines}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.26},
  URN =		{urn:nbn:de:0030-drops-94890},
  doi =		{10.4230/LIPIcs.ESA.2018.26},
  annote =	{Keywords: online algorithms, competitive analysis, minimum makespan scheduling, job migration}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.21
Online Packet Scheduling with Bounded Delay and Lookahead

Authors: Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.
Cite as

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.ISAAC.2016.21,
  author =	{B\"{o}hm, Martin and Chrobak, Marek and Jez, Lukasz and Li, Fei and Sgall, Jir{\'\i} and Vesel\'{y}, Pavel},
  title =	{{Online Packet Scheduling with Bounded Delay and Lookahead}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.21},
  URN =		{urn:nbn:de:0030-drops-67901},
  doi =		{10.4230/LIPIcs.ISAAC.2016.21},
  annote =	{Keywords: buffer management, online scheduling, online algorithm, lookahead}
}
  • Refine by Author
  • 1 Böhm, Martin
  • 1 Chrobak, Marek
  • 1 Englert, Matthias
  • 1 Heinzl, Christoph
  • 1 Jez, Lukasz
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Data Structures
  • 1 Interaction
  • 1 Laman graphs
  • 1 Materials Science
  • 1 Visual Computing
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2019
  • 1 2016
  • 1 2018

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