19 Search Results for "W�hlisch, Matthias"


Document
The Localized Union-Of-Balls Bifiltration

Authors: Michael Kerber and Matthias Söls

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point q, we focus our attention to a ball centered at q whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the q-ball, and a relative variant where the homology of the q-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not k-critical for any finite k. Nevertheless, we demonstrate that these bifiltrations can be computed exactly and efficiently, and we provide a prototypical implementation using the CGAL library. We also argue that some of the recent algorithmic advances for 2-parameter persistence (which usually assume k-criticality for some finite k) carry over to the ∞-critical case.

Cite as

Michael Kerber and Matthias Söls. The Localized Union-Of-Balls Bifiltration. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2023.45,
  author =	{Kerber, Michael and S\"{o}ls, Matthias},
  title =	{{The Localized Union-Of-Balls Bifiltration}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.45},
  URN =		{urn:nbn:de:0030-drops-178953},
  doi =		{10.4230/LIPIcs.SoCG.2023.45},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Persistent Local Homology}
}
Document
Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints

Authors: Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt, and Matthias Weidlich

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)


Abstract
We introduce subsequence-queries with wildcards and gap-size constraints (swg-queries, for short) as a tool for querying event traces. An swg-query q is given by a string s over an alphabet of variables and types, a global window size w, and a tuple c = ((c^-_1, c^+_1), (c^-_2, c^+_2), …, (c^-_{|s|-1}, c^+_{|s|-1})) of local gap-size constraints over ℕ × (ℕ ∪ {∞}). The query q matches in a trace t (i. e., a sequence of types) if the variables can uniformly be substituted by types such that the resulting string occurs in t as a subsequence that spans an area of length at most w, and the i^{th} gap of the subsequence (i. e., the distance between the i^{th} and (i+1)^{th} position of the subsequence) has length at least c^-_i and at most c^+_i. We formalise and investigate the task of discovering an swg-query that describes best the traces from a given sample S of traces, and we present an algorithm solving this task. As a central component, our algorithm repeatedly solves the matching problem (i. e., deciding whether a given query q matches in a given trace t), which is an NP-complete problem (in combined complexity). Hence, the matching problem is of special interest in the context of query discovery, and we therefore subject it to a detailed (parameterised) complexity analysis to identify tractable subclasses, which lead to tractable subclasses of the discovery problem as well. We complement this by a reduction proving that any query discovery algorithm also yields an algorithm for the matching problem. Hence, lower bounds on the complexity of the matching problem directly translate into according lower bounds of the query discovery problem. As a proof of concept, we also implemented a prototype of our algorithm and tested it on real-world data.

Cite as

Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt, and Matthias Weidlich. Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kleestmeiner_et_al:LIPIcs.ICDT.2022.18,
  author =	{Kleest-Mei{\ss}ner, Sarah and Sattler, Rebecca and Schmid, Markus L. and Schweikardt, Nicole and Weidlich, Matthias},
  title =	{{Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.18},
  URN =		{urn:nbn:de:0030-drops-158922},
  doi =		{10.4230/LIPIcs.ICDT.2022.18},
  annote =	{Keywords: event queries on traces, pattern queries on strings, learning descriptive queries, complexity of query evaluation and query learning}
}
Document
Track A: Algorithms, Complexity and Games
Using a Geometric Lens to Find k Disjoint Shortest Paths

Authors: Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1,t_1), …, (s_k,t_k), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_1, …, P_k such that P_i is a shortest s_i-t_i-path for each i ∈ [k]. Recently, Lochet [SODA '21] provided an algorithm that solves k-DSP in n^{O(k^{5^k})} time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(kn^{16k ⋅ k! + k + 1})-time algorithm based on a novel geometric view on this problem. For the special case k = 2, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.

Cite as

Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ICALP.2021.26,
  author =	{Bentert, Matthias and Nichterlein, Andr\'{e} and Renken, Malte and Zschoche, Philipp},
  title =	{{Using a Geometric Lens to Find k Disjoint Shortest Paths}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.26},
  URN =		{urn:nbn:de:0030-drops-140954},
  doi =		{10.4230/LIPIcs.ICALP.2021.26},
  annote =	{Keywords: graph algorithms, dynamic programming, W\lbrack1\rbrack-hardness, geometry}
}
Document
Media Exposition
Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
We illustrate and animate the classic problem of deciding whether a given graph has an Eulerian path. Starting with a collection of instances of increasing difficulty, we present a set of pictorial instructions, and show how they can be used to solve all instances. These IDEA instructions ("A series of nonverbal algorithm assembly instructions") have proven to be both entertaining for experts and enlightening for novices. We (w)rap up with a song and dance to Euler’s original instance.

Cite as

Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt. Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2021.62,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Konitzny, Matthias and Morr, Sebastian and Schmidt, Arne},
  title =	{{Can You Walk This? Eulerian Tours and IDEA Instructions}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{62:1--62:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.62},
  URN =		{urn:nbn:de:0030-drops-138616},
  doi =		{10.4230/LIPIcs.SoCG.2021.62},
  annote =	{Keywords: Eulerian tours, algorithms, education, IDEA instructions}
}
Document
Physical Modeling of Process Forces in Grinding

Authors: Praveen Sridhar, Daniel Mannherz, Raphael Bilz, Kristin M. de Payrebrune, Mahesh R.G. Prasad, and Juan Manuel Rodríguez Prieto

Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)


Abstract
This paper deals with material removal mechanisms in grinding by considering single grit-workpiece interactions. Individual investigations were performed both experimentally and using finite element simulations. Firstly, a comparison between the Johnson-Cooke material model and a Crystal Plasticity finite element method was performed with the help of micro-indentation experiments. Here the research question was answered if an anisotropic material model better describe the grinding process and process forces compared to an isotropic material model. Secondly, four discretization approaches were employed: pure Lagrangian (LAG), Arbitrary Lagrange Eulerian (ALE), Particle Finite Element Method (PFEM), and Smooth Particle Hydrodynamics (SPH), to simulate a micro-cutting operation of A2024 T351 aluminium. This study aims to compare the conventional approaches (LAG and ALE) to newer approaches (PFEM and SPH). The orthogonal cutting models were benchmarked against a micro-cutting experiment presented in literature, by comparing the obtained cutting and passive forces. The study was then extended to negative rake angles to study the effect on the discretization approaches for grinding. Thirdly, scratch experiments were investigated for a brittle material sodalime glass and A2024 T351 aluminium. Effects of the linear speed of the device, depth of cut, and conical tool angle were analyzed and tendencies are built. Finally, a realistic simulation of the manufacturing process of a grinding wheel was developed, starting with the raw material, compression, sintering, and dressing until the final grinding surface. As a result of the simulations, virtual grinding wheel topographies can be visualized and analyzed with regard to the output variables from grinding wheels such as bonding strength and static grain count. The individual research studies help in understanding the material removal mechanisms in a single grit scratch process as well as in the understanding of the overall grinding wheel topography. This in turn helps in the developing an overall physical force model for scratching/grinding to predict mechanical output parameters and hence reduce the need for experimentation.

Cite as

Praveen Sridhar, Daniel Mannherz, Raphael Bilz, Kristin M. de Payrebrune, Mahesh R.G. Prasad, and Juan Manuel Rodríguez Prieto. Physical Modeling of Process Forces in Grinding. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{sridhar_et_al:OASIcs.iPMVM.2020.16,
  author =	{Sridhar, Praveen and Mannherz, Daniel and Bilz, Raphael and de Payrebrune, Kristin M. and Prasad, Mahesh R.G. and Prieto, Juan Manuel Rodr{\'\i}guez},
  title =	{{Physical Modeling of Process Forces in Grinding}},
  booktitle =	{2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)},
  pages =	{16:1--16:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-183-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{89},
  editor =	{Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.16},
  URN =		{urn:nbn:de:0030-drops-137651},
  doi =		{10.4230/OASIcs.iPMVM.2020.16},
  annote =	{Keywords: grinding, single grit approach, finite element method, smooth particle hydrodynamics, particle finite element method, scratch experiments, virtual grinding wheel model}
}
Document
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

Authors: Matthias Bentert, Klaus Heeger, and Dušan Knop

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)


Abstract
In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.

Cite as

Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ISAAC.2020.36,
  author =	{Bentert, Matthias and Heeger, Klaus and Knop, Du\v{s}an},
  title =	{{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36},
  URN =		{urn:nbn:de:0030-drops-133800},
  doi =		{10.4230/LIPIcs.ISAAC.2020.36},
  annote =	{Keywords: Edge-disjoint paths, pathwidth, feedback vertex number}
}
Document
Resolving Infeasibility of Linear Systems: A Parameterized Approach

Authors: Alexander Göke, Lydia Mirabel Mendoza Cadena, and Matthias Mnich

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)


Abstract
Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to inaccuracies of the data or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k)* m^{O(1)}. On the one hand, we establish parameterized intractability (W[1]-hardness) results even in very restricted settings. On the other hand, we develop fixed-parameter algorithms parameterized by the number of perturbed inequalities and the number of positive/negative right-hand sides. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008).

Cite as

Alexander Göke, Lydia Mirabel Mendoza Cadena, and Matthias Mnich. Resolving Infeasibility of Linear Systems: A Parameterized Approach. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{goke_et_al:LIPIcs.IPEC.2019.17,
  author =	{G\"{o}ke, Alexander and Mendoza Cadena, Lydia Mirabel and Mnich, Matthias},
  title =	{{Resolving Infeasibility of Linear Systems: A Parameterized Approach}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.17},
  URN =		{urn:nbn:de:0030-drops-114787},
  doi =		{10.4230/LIPIcs.IPEC.2019.17},
  annote =	{Keywords: Infeasible subsystems, linear programming, fixed-parameter algorithms}
}
Document
Secure Routing for the Internet (Dagstuhl Seminar 18242)

Authors: Philippa Gill, Adrian Perrig, and Matthias Wählisch

Published in: Dagstuhl Reports, Volume 8, Issue 6 (2019)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18242 "Secure Routing for the Internet", which ran from Monday 11/6 (morning) to Wednesday 13/6 (noon), and employed 27 participants in total (including 3 network operators).

Cite as

Philippa Gill, Adrian Perrig, and Matthias Wählisch. Secure Routing for the Internet (Dagstuhl Seminar 18242). In Dagstuhl Reports, Volume 8, Issue 6, pp. 40-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{gill_et_al:DagRep.8.6.40,
  author =	{Gill, Philippa and Perrig, Adrian and W\"{a}hlisch, Matthias},
  title =	{{Secure Routing for the Internet (Dagstuhl Seminar 18242)}},
  pages =	{40--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{6},
  editor =	{Gill, Philippa and Perrig, Adrian and W\"{a}hlisch, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.6.40},
  URN =		{urn:nbn:de:0030-drops-100927},
  doi =		{10.4230/DagRep.8.6.40},
  annote =	{Keywords: Anonymity, BGP, BGP Prefix Hijack, Denial of Service, Deployment Incentives, Detection, Monitoring, Network Operations, Privacy, Protocol, Public Key Infrastructure, Routing, Routing Policy, Routing Security, Testbed}
}
Document
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

Authors: Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/NDP is currently not well understood; the best known lower bound is Omega(log^{1/2 - varepsilon} n), assuming NP not subseteq ZPTIME(n^{poly log n}). This constitutes a significant gap to the best known approximation upper bound of O(n^1/2) due to Chekuri et al. (2006) and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica, 1987) introduce the technique of randomized rounding for LPs; their technique gives an O(1)-approximation when edges (or nodes) may be used by O(log n/log log n) paths. In this paper, we strengthen the above fundamental results. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following. - For MaxEDP, we give an O(r^0.5 log^1.5 kr)-approximation algorithm. As r<=n, up to logarithmic factors, our result strengthens the best known ratio O(n^0.5) due to Chekuri et al. - Further, we show how to route Omega(opt) pairs with congestion O(log(kr)/log log(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson. - For MaxNDP, we give an algorithm that gives the optimal answer in time (k+r)^O(r)n. This is a substantial improvement on the run time of 2^kr^O(r)n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is NP-hard even for r=1, and MaxNDP is W[1]-hard for parameter r. This shows that neither problem is fixed-parameter tractable in r unless FPT = W[1] and that our approximability results are relevant even for very small constant values of r.

Cite as

Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{fleszar_et_al:LIPIcs.ESA.2016.42,
  author =	{Fleszar, Krzysztof and Mnich, Matthias and Spoerhase, Joachim},
  title =	{{New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.42},
  URN =		{urn:nbn:de:0030-drops-63542},
  doi =		{10.4230/LIPIcs.ESA.2016.42},
  annote =	{Keywords: disjoint paths, approximation algorithms, feedback vertex set}
}
Document
Linear-Time Recognition of Map Graphs with Outerplanar Witness

Authors: Matthias Mnich, Ignaz Rutter, and Jens M. Schmidt

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)


Abstract
Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Omega(n^{120}) for n-vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.

Cite as

Matthias Mnich, Ignaz Rutter, and Jens M. Schmidt. Linear-Time Recognition of Map Graphs with Outerplanar Witness. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.SWAT.2016.5,
  author =	{Mnich, Matthias and Rutter, Ignaz and Schmidt, Jens M.},
  title =	{{Linear-Time Recognition of Map Graphs with Outerplanar Witness}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.5},
  URN =		{urn:nbn:de:0030-drops-60349},
  doi =		{10.4230/LIPIcs.SWAT.2016.5},
  annote =	{Keywords: Algorithms and data structures, map graphs, recognition, planar graphs}
}
Document
Parameterized Complexity Dichotomy for Steiner Multicut

Authors: Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

Cite as

Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 157-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.STACS.2015.157,
  author =	{Bringmann, Karl and Hermelin, Danny and Mnich, Matthias and van Leeuwen, Erik Jan},
  title =	{{Parameterized Complexity Dichotomy for Steiner Multicut}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{157--170},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.157},
  URN =		{urn:nbn:de:0030-drops-49115},
  doi =		{10.4230/LIPIcs.STACS.2015.157},
  annote =	{Keywords: graph cut problems, Steiner cut, fixed-parameter tractability}
}
Document
Generalized Reordering Buffer Management

Authors: Yossi Azar, Matthias Englert, Iftah Gamzu, and Eytan Kidron

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


Abstract
An instance of the generalized reordering buffer management problem consists of a service station that has k servers, each configured with a color, and a buffer of size b. The station needs to serve an online stream of colored items. Whenever an item arrives, it is stored in the buffer. At any point in time, a currently pending item can be served by switching a server to its color. The objective is to serve all items in a way that minimizes the number of servers color switches. This problem generalizes two well-studied online problems: the paging problem, which is the special case when b=1, and the reordering buffer problem, which is the special case when k=1. In this paper, we develop a randomized online algorithm that obtains a competitive ratio of O(sqrt(b).ln(k)). Note that this result beats the easy deterministic lower bound of k whenever b < k^(2-e). We complement our randomized approach by presenting a deterministic algorithm that attains a competitive ratio of O(min{k^2.ln(b),k.b}). We further demonstrate that if our deterministic algorithm can employ k/(1-d) servers where d is in (0,1), then it achieves a competitive ratio of O(min{ln(b/d^2),b/d}) against an optimal offline adversary that employs k servers.

Cite as

Yossi Azar, Matthias Englert, Iftah Gamzu, and Eytan Kidron. Generalized Reordering Buffer Management. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 87-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.STACS.2014.87,
  author =	{Azar, Yossi and Englert, Matthias and Gamzu, Iftah and Kidron, Eytan},
  title =	{{Generalized Reordering Buffer Management}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{87--98},
  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.87},
  URN =		{urn:nbn:de:0030-drops-44498},
  doi =		{10.4230/LIPIcs.STACS.2014.87},
  annote =	{Keywords: online algorithms, paging, reordering buffer}
}
Document
The Critical Internet Infrastructure (Dagstuhl Seminar 13322)

Authors: Georg Carle, Jochen Schiller, Steve Uhlig, Walter Willinger, and Matthias Wählisch

Published in: Dagstuhl Reports, Volume 3, Issue 8 (2013)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13322 "The Critical Internet Infrastructure". The scope of the seminar includes three main topics, rethinking perspectives on the Internet backbone, methodologies to analyze the Internet structure, and paradigms overlaying IP connectivity. The results are based on fruitful discussions between people from the research and operational community.

Cite as

Georg Carle, Jochen Schiller, Steve Uhlig, Walter Willinger, and Matthias Wählisch. The Critical Internet Infrastructure (Dagstuhl Seminar 13322). In Dagstuhl Reports, Volume 3, Issue 8, pp. 27-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{carle_et_al:DagRep.3.8.27,
  author =	{Carle, Georg and Schiller, Jochen and Uhlig, Steve and Willinger, Walter and W\"{a}hlisch, Matthias},
  title =	{{The Critical Internet Infrastructure (Dagstuhl Seminar 13322)}},
  pages =	{27--39},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{8},
  editor =	{Carle, Georg and Schiller, Jochen and Uhlig, Steve and Willinger, Walter and W\"{a}hlisch, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.8.27},
  URN =		{urn:nbn:de:0030-drops-43416},
  doi =		{10.4230/DagRep.3.8.27},
  annote =	{Keywords: Internet, Backbone, Internet Services, Critical Infrastructure}
}
Document
Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361)

Authors: Ali Ghodsi, Börje Ohlman, Jörg Ott, Ignacio Solis, and Matthias Wählisch

Published in: Dagstuhl Reports, Volume 2, Issue 9 (2013)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12361 ``Information-centric networking -- Ready for the real world?''. The outcome of this seminar is based on individual talks, group work, and significant discussions among all participants. The topics range from application and performance aspects up to business, legal, and deployment questions. Even though significant progress is visible from the last Dagstuhl Seminar about ICN, there are still thrilling open research questions in all topic areas.

Cite as

Ali Ghodsi, Börje Ohlman, Jörg Ott, Ignacio Solis, and Matthias Wählisch. Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361). In Dagstuhl Reports, Volume 2, Issue 9, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{ghodsi_et_al:DagRep.2.9.1,
  author =	{Ghodsi, Ali and Ohlman, B\"{o}rje and Ott, J\"{o}rg and Solis, Ignacio and W\"{a}hlisch, Matthias},
  title =	{{Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{9},
  editor =	{Ghodsi, Ali and Ohlman, B\"{o}rje and Ott, J\"{o}rg and Solis, Ignacio and W\"{a}hlisch, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.9.1},
  URN =		{urn:nbn:de:0030-drops-37877},
  doi =		{10.4230/DagRep.2.9.1},
  annote =	{Keywords: Information-centric, Network architecture, Application structure, Internet business models}
}
Document
Economical Caching

Authors: Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)


Abstract
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is given a price from the interval $[1,\alpha]$, a consumption, and possibly a buying limit. The online algorithm has to decide the amount to purchase from some commodity, knowing the parameter $\alpha$ but without knowing how the price evolves in the future. The algorithm can purchase at most the buying limit. If it purchases more than the current consumption, then the excess is stored in the storage; otherwise, the gap between consumption and purchase must be taken from the storage. The goal is to minimize the total cost. Interesting applications are, for example, stream caching on mobile devices with different classes of service, battery management in micro hybrid cars, and the efficient purchase of resources. First we consider the simple but natural class of algorithms that can informally be described as memoryless. We show that these algorithms cannot achieve a competitive ratio below $\sqrt{\alpha}$. Then we present a more sophisticated deterministic algorithm achieving a competitive ratio of \[\textstyle \frac{1}{W\left(\frac{1-\alpha}{e\alpha}\right)+1} \in \left[\frac{\sqrt{\alpha}}{\sqrt{2}}, \frac{\sqrt{\alpha}+1}{\sqrt{2}} \right] \enspace, \] where $W$ denotes the Lambert~W function. We prove that this algorithm is optimal and that not even randomized online algorithms can achieve a better competitive ratio. On the other hand, we show how to achieve a constant competitive ratio if the storage capacity of the online algorithm exceeds the storage capacity of an optimal offline algorithm by a factor of $\log \alpha$.

Cite as

Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking. Economical Caching. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 385-396, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{englert_et_al:LIPIcs.STACS.2009.1826,
  author =	{Englert, Matthias and R\"{o}glin, Heiko and Sp\"{o}nemann, Jacob and V\"{o}cking, Berthold},
  title =	{{Economical Caching}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{385--396},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1826},
  URN =		{urn:nbn:de:0030-drops-18263},
  doi =		{10.4230/LIPIcs.STACS.2009.1826},
  annote =	{Keywords: Online algorithms, Competitive analysis, Storage management}
}
  • Refine by Author
  • 4 Mnich, Matthias
  • 3 Grumer, Matthias
  • 3 Steger, Christian
  • 3 Wendt, Manuel
  • 3 Wählisch, Matthias
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Applied computing → Education
  • 1 Computing methodologies → Modeling and simulation
  • 1 Information systems → Data mining
  • Show More...

  • Refine by Keyword
  • 1 Algorithms and data structures
  • 1 Anonymity
  • 1 Application structure
  • 1 BGP
  • 1 BGP Prefix Hijack
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 3 2007
  • 3 2021
  • 2 2013
  • 2 2016
  • 2 2019
  • 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