12 Search Results for "M�nz, Gerhard"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.12
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Authors: Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot

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

Abstract
We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(n log n + mn + m²) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.
Cite as

Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.SoCG.2022.12,
  author =	{Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn},
  title =	{{Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{12:1--12:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.12},
  URN =		{urn:nbn:de:0030-drops-160203},
  doi =		{10.4230/LIPIcs.SoCG.2022.12},
  annote =	{Keywords: motion planning, computational geometry, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.19
An Investigation of the Recoverable Robust Assignment Problem

Authors: Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2-k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.
Cite as

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
  author =	{Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{An Investigation of the Recoverable Robust Assignment Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154025},
  doi =		{10.4230/LIPIcs.IPEC.2021.19},
  annote =	{Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.20
Graph Similarity and Approximate Isomorphism

Authors: Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G,H of the same order n with adjacency matrices A_G,A_H, a well-studied measure of similarity is the Frobenius distance dist(G,H):=min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.
Cite as

Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph Similarity and Approximate Isomorphism. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.MFCS.2018.20,
  author =	{Grohe, Martin and Rattan, Gaurav and Woeginger, Gerhard J.},
  title =	{{Graph Similarity and Approximate Isomorphism}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.20},
  URN =		{urn:nbn:de:0030-drops-96021},
  doi =		{10.4230/LIPIcs.MFCS.2018.20},
  annote =	{Keywords: Graph Similarity, Quadratic Assignment Problem, Approximate Graph Isomorphism}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.5
Fine-Grained Complexity Analysis of Two Classic TSP Variants

Authors: Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. Our first set of results is motivated by the Bitonic tsp problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamicprogramming exercise to solve this problem in O(n^2) time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Fréchet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic tsp in O(n*log^2(n)) time and its bottleneck version in O(n*log^3(n)) time. In the more general pyramidal tsp problem, the points to be visited are labeled 1, ..., n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) tsp problem also work for the pyramidal tsp problem in the plane. Our second set of results concerns the popular k-opt heuristic for tsp in the graph setting. More precisely, we study the k-opt decision problem, which asks whether a given tour can be improved by a k-opt move that replaces k edges in the tour by k new edges. A simple algorithm solves k-opt in O(n^k) time for fixed k. For 2-opt, this is easily seen to be optimal. For k = 3 we prove that an algorithm with a runtime of the form ~O(n^{3-epsilon}) exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. For general k-opt, it is known that a runtime of f(k)*n^{o(k/log(k))} would contradict the Exponential Time Hypothesis. The results for k = 2, 3 may suggest that the actual time complexity of k-opt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best k-move in O(n^{lfoor 2k/3 rfloor +1}) time for fixed k >= 3. This implies that 4-opt can be solved in O(n^3) time, matching the best-known algorithm for 3-opt. Finally, we show how to beat the quadratic barrier for k = 2 in two important settings, namely for points in the plane and when we want to solve 2-opt repeatedly
Cite as

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger. Fine-Grained Complexity Analysis of Two Classic TSP Variants. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ICALP.2016.5,
  author =	{de Berg, Mark and Buchin, Kevin and Jansen, Bart M. P. and Woeginger, Gerhard},
  title =	{{Fine-Grained Complexity Analysis of Two Classic TSP Variants}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.5},
  URN =		{urn:nbn:de:0030-drops-62770},
  doi =		{10.4230/LIPIcs.ICALP.2016.5},
  annote =	{Keywords: Traveling salesman problem, fine-grained complexity, bitonic tours, k-opt}
}
Document
DOI: 10.4230/OASIcs.KiVS.2011.61
Improving Markov-based TCP Traffic Classification

Authors: Gerhard Münz, Stephan Heckmüller, Lothar Braun, and Georg Carle

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)

Abstract
This paper presents an improved variant of our Markov-based TCP traffic classifier and demonstrates its performance using traffic captured in a university network. Payload length, flow direction, and position of the first data packets of a TCP connection are reflected in the states of the Markov models. In addition, we integrate a new "end of connection" state to further improve the classification accuracy. Using 10-fold cross validation, we identify appropriate settings for the payload length intervals and the number of data packets considered in the models. Finally, we discuss the classification results for the different applications.
Cite as

Gerhard Münz, Stephan Heckmüller, Lothar Braun, and Georg Carle. Improving Markov-based TCP Traffic Classification. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{munz_et_al:OASIcs.KiVS.2011.61,
  author =	{M\"{u}nz, Gerhard and Heckm\"{u}ller, Stephan and Braun, Lothar and Carle, Georg},
  title =	{{Improving Markov-based TCP Traffic Classification}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{61--72},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.61},
  URN =		{urn:nbn:de:0030-drops-29582},
  doi =		{10.4230/OASIcs.KiVS.2011.61},
  annote =	{Keywords: Markov model, TCP Traffic Classification, network}
}
Document
DOI: 10.4230/DagSemProc.10081.13
Research with Collaborative Unmanned Aircraft Systems

Authors: Patrick Doherty, Jonas Kvarnström, Fredrik Heintz, D. Landen, and P.-M. Olsson

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
We provide an overview of ongoing research which targets development of a principled framework for mixed-initiative interaction with unmanned aircraft systems (UAS). UASs are now becoming technologically mature enough to be integrated into civil society. Principled interaction between UASs and human resources is an essential component in their future uses in complex emergency services or bluelight scenarios. In our current research, we have targeted a triad of fundamental, interdependent conceptual issues: delegation, mixed- initiative interaction and adjustable autonomy, that is being used as a basis for developing a principled and well-defined framework for interaction. This can be used to clarify, validate and verify different types of interaction between human operators and UAS systems both theoretically and practically in UAS experimentation with our deployed platforms.
Cite as

Patrick Doherty, Jonas Kvarnström, Fredrik Heintz, D. Landen, and P.-M. Olsson. Research with Collaborative Unmanned Aircraft Systems. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doherty_et_al:DagSemProc.10081.13,
  author =	{Doherty, Patrick and Kvarnstr\"{o}m, Jonas and Heintz, Fredrik and Landen, D. and Olsson, P.-M.},
  title =	{{Research with Collaborative Unmanned Aircraft Systems}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.13},
  URN =		{urn:nbn:de:0030-drops-26300},
  doi =		{10.4230/DagSemProc.10081.13},
  annote =	{Keywords: Multi-agent systems, robotics, human-robot interaction, delegation}
}
Document
DOI: 10.4230/DagSemProc.10081.16
Stream-Based Reasoning in DyKnow

Authors: Fredrik Heintz, Jonas Kvarnström, and Patrick Doherty

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
The information available to modern autonomous systems is often in the form of streams. As the number of sensors and other stream sources increases there is a growing need for incremental reasoning about the incomplete content of sets of streams in order to draw relevant conclusions and react to new situations as quickly as possible. To act rationally, autonomous agents often depend on high level reasoning components that require crisp, symbolic knowledge about the environment. Extensive processing at many levels of abstraction is required to generate such knowledge from noisy, incomplete and quantitative sensor data. We define knowledge processing middleware as a systematic approach to integrating and organizing such processing, and argue that connecting processing components with streams provides essential support for steady and timely flows of information. DyKnow is a concrete and implemented instantiation of such middleware, providing support for stream reasoning at several levels. First, the formal kpl language allows the specification of streams connecting knowledge processes and the required properties of such streams. Second, chronicle recognition incrementally detects complex events from streams of more primitive events. Third, complex metric temporal formulas can be incrementally evaluated over streams of states. DyKnow and the stream reasoning techniques are described and motivated in the context of a UAV traffic monitoring application.
Cite as

Fredrik Heintz, Jonas Kvarnström, and Patrick Doherty. Stream-Based Reasoning in DyKnow. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{heintz_et_al:DagSemProc.10081.16,
  author =	{Heintz, Fredrik and Kvarnstr\"{o}m, Jonas and Doherty, Patrick},
  title =	{{Stream-Based Reasoning in DyKnow}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.16},
  URN =		{urn:nbn:de:0030-drops-26274},
  doi =		{10.4230/DagSemProc.10081.16},
  annote =	{Keywords: Knowledge representation, autonomous systems, stream-based reasoning}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/DagSemProc.07462.15
Multimodal Interaction for Ambient Assisted Living (AAL)

Authors: Max Mühlhäuser

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

Abstract
Ambient Assisted Living calls for considerable advancements in user interfaces, compared to conventional computers and applications. Multimodal interaction plays an important role in this context. The contribution start from the broader perspective of ambient intelligence and ubiquitous computing, discussing major requirements imposed on multimodal interaction and interactive software development. These more general requirements are then briefly revised with respect to AAL specific issues.
Cite as

Max Mühlhäuser. Multimodal Interaction for Ambient Assisted Living (AAL). In Assisted Living Systems - Models, Architectures and Engineering Approaches. Dagstuhl Seminar Proceedings, Volume 7462, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{muhlhauser:DagSemProc.07462.15,
  author =	{M\"{u}hlh\"{a}user, Max},
  title =	{{Multimodal Interaction for Ambient Assisted Living (AAL)}},
  booktitle =	{Assisted Living Systems - Models, Architectures and Engineering Approaches},
  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.15},
  URN =		{urn:nbn:de:0030-drops-14707},
  doi =		{10.4230/DagSemProc.07462.15},
  annote =	{Keywords: HCI, User Interfaces, Multimodality, Ambient Intelligence, Ambient Assisted Living}
}
Document
DOI: 10.4230/DagSemProc.07462.24
Software Development Support for Ambient Assisted Living

Authors: Max Mühlhäuser

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

Abstract
Key issues in software development support for Ambient Intelligence and Ubiquitous Computing are briefly discussed; special requirements in the context of Ambient Assisted Living are discussed.
Cite as

Max Mühlhäuser. Software Development Support for Ambient Assisted Living. In Assisted Living Systems - Models, Architectures and Engineering Approaches. Dagstuhl Seminar Proceedings, Volume 7462, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{muhlhauser:DagSemProc.07462.24,
  author =	{M\"{u}hlh\"{a}user, Max},
  title =	{{Software Development Support for Ambient Assisted Living}},
  booktitle =	{Assisted Living Systems - Models, Architectures and Engineering Approaches},
  pages =	{1--3},
  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.24},
  URN =		{urn:nbn:de:0030-drops-14691},
  doi =		{10.4230/DagSemProc.07462.24},
  annote =	{Keywords: Software Development, Ambient Intelligence, Ubiquitous Computing, Ambient Assisted Living}
}
Document
DOI: 10.4230/DagSemProc.07261.10
Maximizing the Minimum Load for Selfisch Agents

Authors: Leah Epstein and Rob van Stee

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
We consider the problem of maximizing the minimum load for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. Unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. For a constant number of machines, $m$, we show a monotone polynomial time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We also present an FPTAS for the classical machine covering problem, i.e., where no selfish agents are involved (the previous best result for this case was a PTAS) and use this to give a monotone FPTAS. Additionally, we give a monotone approximation algorithm with approximation ratio $min(m,(2+eps)s_1/s_m)$ where $eps>0$ can be chosen arbitrarily small and $s_i$ is the (real) speed of machine $i$. Finally we give improved results for two machines.
Cite as

Leah Epstein and Rob van Stee. Maximizing the Minimum Load for Selfisch Agents. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:DagSemProc.07261.10,
  author =	{Epstein, Leah and van Stee, Rob},
  title =	{{Maximizing the Minimum Load for Selfisch Agents}},
  booktitle =	{Fair Division},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.10},
  URN =		{urn:nbn:de:0030-drops-12427},
  doi =		{10.4230/DagSemProc.07261.10},
  annote =	{Keywords: Scheduling, algorithmic mechanism design, maximizing minimum load}
}
Document
DOI: 10.4230/DagSemProc.05391.5
Integration of reliable algorithms into modeling software

Authors: Wolfram Luther, Gerhard Haßlinger, Ekaterina Auer, Eva Dyllong, Daniela Traczinski, and Holger Traczinski

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

Abstract
In this note we discuss strategies that would enhance modern modeling and simulation software (MSS) with reliable routines using validated data types, controlled rounding, algorithmic differentiation and interval equation or initial value problem solver. Several target systems are highlighted. In stochastic traffic modeling, the computation of workload distributions plays a prominent role since they influence the quality of service parameters. INoWaTIV is a workload analysis tool that uses two different techniques: the polynomial factorization approach and the Wiener-Hopf factorization to determine the work-load distributions of GI/GI/1 and SMP/GI/1 service systems accurately. Two extensions of a multibody modeling and simulation software were developed to model kinematic and dynamic properties of multibody systems in a validated way. Furthermore, an interface was created that allows the computation of convex hulls and reliable lower bounds for the distances between subpav-ing-encoded objects constructed with SIVIA (Set Inverter Via Interval Analysis).
Cite as

Wolfram Luther, Gerhard Haßlinger, Ekaterina Auer, Eva Dyllong, Daniela Traczinski, and Holger Traczinski. Integration of reliable algorithms into modeling software. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{luther_et_al:DagSemProc.05391.5,
  author =	{Luther, Wolfram and Ha{\ss}linger, Gerhard and Auer, Ekaterina and Dyllong, Eva and Traczinski, Daniela and Traczinski, Holger},
  title =	{{Integration of reliable algorithms into modeling software}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.5},
  URN =		{urn:nbn:de:0030-drops-4441},
  doi =		{10.4230/DagSemProc.05391.5},
  annote =	{Keywords: Reliable algorithms, stochastic traffic modeling, multibody modeling tools, geometric modeling}
}
  • Refine by Author
  • 3 Woeginger, Gerhard J.
  • 2 Buchin, Kevin
  • 2 Doherty, Patrick
  • 2 Heintz, Fredrik
  • 2 Kvarnström, Jonas
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 2 Ambient Assisted Living
  • 2 Ambient Intelligence
  • 1 Approximate Graph Isomorphism
  • 1 Graph Similarity
  • 1 HCI
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 3 2010
  • 2 2008
  • 1 2006
  • 1 2007
  • 1 2011
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact