6 Search Results for "Jünger, Michael"

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-dev.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-dev.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-dev.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-dev.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-dev.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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.197},
  URN =		{urn:nbn:de:0030-drops-150832},
  doi =		{10.4230/DagSemRep.197},
}
  • Refine by Author
  • 6 Jünger, Michael
  • 2 Kobourov, Stephen
  • 2 Mutzel, Petra
  • 2 Reinelt, Gerhard
  • 2 Rieger, Heiko
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Integer programming
  • 1 Mathematics of computing → Linear programming

  • Refine by Keyword
  • 1 Binary quadratic optimization
  • 1 Graph Drawing
  • 1 Graph drawing
  • 1 Integer linear programming
  • 1 Interactive Visualization
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2006
  • 1 1998
  • 1 2000
  • 1 2001
  • 1 2019

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