Search Results

Documents authored by Jünger, Michael

Document
DOI: 10.4230/LIPIcs.GD.2024.31
Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings

Authors: Alexander Dobler, Michael Jünger, Paul J. Jünger, Julian Meffert, Petra Mutzel, and Martin Nöllenburg

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Storyline drawings are a popular visualization of interactions of a set of characters over time, e.g., to show participants of scenes in a book or movie. Characters are represented as x-monotone curves that converge vertically for interactions and diverge otherwise. Combinatorially, the task of computing storyline drawings reduces to finding a sequence of permutations of the character curves for the different time points, with the primary objective being crossing minimization of the induced character trajectories. In this paper, we revisit exact integer linear programming (ILP) approaches for this NP-hard problem. By enriching previous formulations with additional problem-specific insights and new heuristics, we obtain exact solutions for an extended new benchmark set of larger and more complex instances than had been used before. Our experiments show that our enriched formulations lead to better performing algorithms when compared to state-of-the–art modelling techniques. In particular, our best algorithms are on average 2.6-3.2 times faster than the state-of-the-art and succeed in solving complex instances that could not be solved before within the given time limit. Further, we show in an ablation study that our enrichment components contribute considerably to the performance of the new ILP formulation.
Cite as

Alexander Dobler, Michael Jünger, Paul J. Jünger, Julian Meffert, Petra Mutzel, and Martin Nöllenburg. Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2024.31,
  author =	{Dobler, Alexander and J\"{u}nger, Michael and J\"{u}nger, Paul J. and Meffert, Julian and Mutzel, Petra and N\"{o}llenburg, Martin},
  title =	{{Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.31},
  URN =		{urn:nbn:de:0030-drops-213159},
  doi =		{10.4230/LIPIcs.GD.2024.31},
  annote =	{Keywords: Storyline drawing, crossing minimization, integer linear programming, algorithm engineering, computational experiments}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.63
Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Authors: Michael Jünger and Sven Mallach

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

Abstract
Solving the NP-hard Maximum Cut or Binary Quadratic Optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.
Cite as

Michael Jünger and Sven Mallach. Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:LIPIcs.ESA.2019.63,
  author =	{J\"{u}nger, Michael and Mallach, Sven},
  title =	{{Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{63:1--63:13},
  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.63},
  URN =		{urn:nbn:de:0030-drops-111840},
  doi =		{10.4230/LIPIcs.ESA.2019.63},
  annote =	{Keywords: Maximum cut, Binary quadratic optimization, Integer linear programming}
}
Document
DOI: 10.4230/DagSemProc.05191.1
05191 Abstracts Collection – Graph Drawing

Authors: Michael Jünger, Petra Mutzel, and Stephen Kobourov

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

Abstract
From 08.05.05 to 13.05.05, the Dagstuhl Seminar 05191 ``Graph Drawing'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Michael Jünger, Petra Mutzel, and Stephen Kobourov. 05191 Abstracts Collection – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.1,
  author =	{J\"{u}nger, Michael and Mutzel, Petra and Kobourov, Stephen},
  title =	{{05191 Abstracts Collection – Graph Drawing}},
  booktitle =	{Graph Drawing},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.1},
  URN =		{urn:nbn:de:0030-drops-3485},
  doi =		{10.4230/DagSemProc.05191.1},
  annote =	{Keywords: Graph Drawing, Visualization, Layout Algorithms, Interactive Visualization}
}
Document
DOI: 10.4230/DagSemProc.05191.2
05191 Executive Summary – Graph Drawing

Authors: Michael Jünger, Stephen Kobourov, and Petra Mutzel

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

Abstract
This paper summarizes the topics, aims, and achievements of the Dagstuhl Seminar 05191 on Graph Drawing.
Cite as

Michael Jünger, Stephen Kobourov, and Petra Mutzel. 05191 Executive Summary – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.2,
  author =	{J\"{u}nger, Michael and Kobourov, Stephen and Mutzel, Petra},
  title =	{{05191 Executive Summary – Graph Drawing}},
  booktitle =	{Graph Drawing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.2},
  URN =		{urn:nbn:de:0030-drops-3420},
  doi =		{10.4230/DagSemProc.05191.2},
  annote =	{Keywords: Graph drawing}
}
Document
DOI: 10.4230/DagSemRep.299
Algorithmic Techniques in Physics (Dagstuhl Seminar 01091)

Authors: Michael Jünger, Gerhard Reinelt, Heiko Rieger, and Giovanni Rinaldi

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

Abstract
Cite as

Michael Jünger, Gerhard Reinelt, Heiko Rieger, and Giovanni Rinaldi. Algorithmic Techniques in Physics (Dagstuhl Seminar 01091). Dagstuhl Seminar Report 299, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{junger_et_al:DagSemRep.299,
  author =	{J\"{u}nger, Michael and Reinelt, Gerhard and Rieger, Heiko and Rinaldi, Giovanni},
  title =	{{Algorithmic Techniques in Physics (Dagstuhl Seminar 01091)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{299},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.299},
  URN =		{urn:nbn:de:0030-drops-151833},
  doi =		{10.4230/DagSemRep.299},
}
Document
DOI: 10.4230/DagSemRep.262
Constraint Programming and Integer Programming (Dagstuhl Seminar 00031)

Authors: Krysztof Apt, Michael Jünger, Pascal van Hentenryck, and Laurence A. Wolsey

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

Abstract
Cite as

Krysztof Apt, Michael Jünger, Pascal van Hentenryck, and Laurence A. Wolsey. Constraint Programming and Integer Programming (Dagstuhl Seminar 00031). Dagstuhl Seminar Report 262, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{apt_et_al:DagSemRep.262,
  author =	{Apt, Krysztof and J\"{u}nger, Michael and van Hentenryck, Pascal and Wolsey, Laurence A.},
  title =	{{Constraint Programming and Integer Programming (Dagstuhl Seminar 00031)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{262},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.262},
  URN =		{urn:nbn:de:0030-drops-151477},
  doi =		{10.4230/DagSemRep.262},
}
Document
DOI: 10.4230/DagSemRep.197
Algorithmic Techniques in Physics (Dagstuhl Seminar 9751)

Authors: Michael Jünger, Gerhard Reinelt, Heiko Rieger, and Giovanni Rinaldi

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

Abstract
Cite as

Michael Jünger, Gerhard Reinelt, Heiko Rieger, and Giovanni Rinaldi. Algorithmic Techniques in Physics (Dagstuhl Seminar 9751). Dagstuhl Seminar Report 197, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{junger_et_al:DagSemRep.197,
  author =	{J\"{u}nger, Michael and Reinelt, Gerhard and Rieger, Heiko and Rinaldi, Giovanni},
  title =	{{Algorithmic Techniques in Physics (Dagstuhl Seminar 9751)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{197},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.197},
  URN =		{urn:nbn:de:0030-drops-150832},
  doi =		{10.4230/DagSemRep.197},
}
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