6 Search Results for "Wolf, Matthias"


Document
Cluster Editing with Overlapping Communities

Authors: Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example, in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Another strong motivation comes from language networks where trying to cluster words with similar usage can be confounded by homonyms, that is, words with multiple meanings like "bat". The recently introduced operation of vertex splitting is one natural approach to incorporating such overlap into Cluster Editing. First used in the context of graph drawing, this operation allows a vertex v to be replaced by two vertices whose combined neighborhood is the neighborhood of v (and thus v can belong to more than one cluster). The problem of transforming a graph into a cluster graph using at most k edge additions, edge deletions, or vertex splits is called Cluster Editing with Vertex Splitting and is known to admit a polynomial kernel with respect to k and an O(9^{k²} + n + m)-time (parameterized) algorithm. However, it was not known whether the problem is NP-hard, a question which was originally asked by Abu-Khzam et al. [Combinatorial Optimization, 2018]. We answer this in the affirmative. We further give an improved algorithm running in O(2^{7klog k} + n + m) time.

Cite as

Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2,
  author =	{Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra},
  title =	{{Cluster Editing with Overlapping Communities}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2},
  URN =		{urn:nbn:de:0030-drops-194218},
  doi =		{10.4230/LIPIcs.IPEC.2023.2},
  annote =	{Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm}
}
Document
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Authors: Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:ℝⁿ → ℝ and its (sub)gradient. Our goal is to find an ε-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)²) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the randomized lower bound of Ω((GR/ε)²) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)²) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.

Cite as

Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2021.53,
  author =	{Garg, Ankit and Kothari, Robin and Netrapalli, Praneeth and Sherif, Suhail},
  title =	{{No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.53},
  URN =		{urn:nbn:de:0030-drops-135921},
  doi =		{10.4230/LIPIcs.ITCS.2021.53},
  annote =	{Keywords: Quantum algorithms, Gradient descent, Convex optimization}
}
Document
Engineering Negative Cycle Canceling for Wind Farm Cabling

Authors: Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf

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


Abstract
In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each cable type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP). We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [Sascha Gritzbach et al., 2018]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP. A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to under two minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning.

Cite as

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gritzbach_et_al:LIPIcs.ESA.2019.55,
  author =	{Gritzbach, Sascha and Ueckerdt, Torsten and Wagner, Dorothea and Wegner, Franziska and Wolf, Matthias},
  title =	{{Engineering Negative Cycle Canceling for Wind Farm Cabling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{55:1--55:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.55},
  URN =		{urn:nbn:de:0030-drops-111766},
  doi =		{10.4230/LIPIcs.ESA.2019.55},
  annote =	{Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning}
}
Document
Efficient Algorithms for Ortho-Radial Graph Drawing

Authors: Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)


Abstract
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. [2017] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.

Cite as

Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{niedermann_et_al:LIPIcs.SoCG.2019.53,
  author =	{Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
  title =	{{Efficient Algorithms for Ortho-Radial Graph Drawing}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.53},
  URN =		{urn:nbn:de:0030-drops-104572},
  doi =		{10.4230/LIPIcs.SoCG.2019.53},
  annote =	{Keywords: Graph Drawing, Ortho-Radial Graph Drawing, Ortho-Radial Representation, Topology-Shape-Metrics, Efficient Algorithms}
}
Document
Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Authors: Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.

Cite as

Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.SoCG.2017.14,
  author =	{Barth, Lukas and Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
  title =	{{Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.14},
  URN =		{urn:nbn:de:0030-drops-72234},
  doi =		{10.4230/LIPIcs.SoCG.2017.14},
  annote =	{Keywords: Graph Drawing, Ortho-Radial Drawings, Combinatorial Characterization, Bend Minimization, Topology-Shape-Metrics}
}
Document
Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland

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

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


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

Cite as

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


Copy BibTex To Clipboard

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

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Network flows
  • 1 Mathematics of computing → Network optimization
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 2 Graph Drawing
  • 2 Topology-Shape-Metrics
  • 1 Bend Minimization
  • 1 Combinatorial Characterization
  • 1 Convex optimization
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2019
  • 1 2006
  • 1 2017
  • 1 2021
  • 1 2023

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