Prof. Dr. Volker Kaibel
Prof. Dr. Volker Kaibel
2024
Steiner Cut Dominants
Conforti, M., Kaibel, V.
Article in Mathematics of Operations Research
Refined TSSOS
Shaydurova, D., Kaibel, V., Sager, S.
Binary Cyclic Transversal Polytopes
Frede, J., Kaibel, V., Merkert, M.
2023
Polytope Extensions with Linear Diameters
Kaibel, V., Kukharenko, K.
Optimal sufficient requirements on the embedded Ising problem in polynomial time
Lobe, E., Kaibel, V.
Article in Quantum Information Processing
2021
Scale-Free Spanning Trees and Their Application in Genomic Epidemiology
Orlovich, Y., Kukharenko, K., Kaibel, V., Skums, P.
Article in Journal of Computational Biology
2020
Correction to: Extended Formulations for Independence Polytopes of Regular Matroids
Kaibel, V., Lee, J., Walter, M., Weltge, S.
Article in Graphs and Combinatorics
2018
Maximum Semidefinite and Linear Extension Complexity of Families of Polytopes
Averkov, G., Kaibel, V., Weltge, S.
Article in Math. Program.
2017
A Note on Matchings Constructed during Edmonds' Weighted Perfect
Kaibel, V., Walter, M.
2016
Extended Formulations for Independence Polytopes of Regular Matroids
Kaibel, V., Lee, J., Walter, M., Weltge, S.
(+++See the erratum in Kaibel et al. 2020+++)
Article in Graphs and Combinatorics
2015
Forbidden Vertices
Angulo, G., Ahmed, S., Dey, S. S., Kaibel, V.
Article in Mathematics of Oper. Res.
Subgraph polytopes and independence polytopes of count matroids
Conforti, M., Kaibel, V., Walter, M., Weltge, S.
Article in Operations Research Letters
The Unimodular Intersection Problem
Kaibel, V., Onn, S., Sarrabezolles, P.
Article in Operations Research Letters
A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
Kaibel, V., Weltge, S.
Article in Discrete and Computational Geometry
Simple extensions of polytopes
Kaibel, V., Walter, M.
Article in Math. Program. Ser. B
Lower Bounds on the Sizes of Integer Programs without Additional Variables
Kaibel, V., Weltge, S.
Article in Math. Program. Ser. B
2014
Simple Extensions of Polytopes
Kaibel, V., Walter, M.
Appeared in Integer Programming and Combinatorial Optimization, 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings
Lower Bounds on the Sizes of Integer Programs without Additional Variables
Kaibel, V., Weltge, S.
Appeared in Integer Programming and Combinatorial Optimization, 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings
2013
Combinatorial Bounds on Nonnegative Rank and Extended Formulations
Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D. O.
Article in Discrete Math.
Which Nonnegative Matrices Are Slack Matrices?
Gouveia, J., Grappe, R., Kaibel, V., Pashkovich, K., Robinson, R. Z., Thomas, R. R.
Article in Linear Algebra Appl.
Constructing Extended Formulations from Reflection Relations
Kaibel, V., Pashkovich, K.
Chapter in Facets of Combinatorial Optimization – Festschrift for Martin Grötschel
2012
Symmetry Matters for Sizes of Extended Formulations
Kaibel, V., Pashkovich, K., Theis, D. O.
Article in SIAM J. Disc. Math.
2011
Basic Polyhedral Theory
Kaibel, V.
Chapter in Wiley Encyclopedia of Operations Research and Management Science
Extended Formulations in Combinatorial Optimization
Kaibel, V.
Finding Descriptions of Polytopes via Extended Formulations and Liftings
Kaibel, V., Loos, A.
Chapter in Progress in Combinatorial Optimization
Constructing Extended Formulations from Reflection Relations
Kaibel, V., Pashkovich, K.
Appeared in Integer Programming and Combinatorial Optimization. Proceedings of IPCO XV, New York, NY
Orbitopal fixing
Kaibel, V., Peinhardt, M., Pfetsch, M. E.
Article in Discr. Opt.
2010
Branched Polyhedral Systems
Kaibel, V., Loos, A.
Appeared in Integer Programming and Combinatorial Optimization. Proceedings of IPCO XIV, Ithaca, NY
Symmetry Matters for the Sizes of Extended Formulations
Kaibel, V., Pashkovich, K., Theis, D. O.
Appeared in Integer Programming and Combinatorial Optimization. Proceedings of IPCO XIV, Ithaca, NY
On cardinality constrained cycle and path polytopes
Kaibel, V., Stephan, R.
Article in Math. Program.
2009
Extended Formulations for Packing and Partitioning Orbitopes
Faenza, Y., Kaibel, V.
Article in Math. Oper. Res.
Another Proof of the Fact that Polyhedral Cones are Finitely Generated
Kaibel, V.
Two Theorems on Projections of Polyhedra
Kaibel, V.
2008
A Short Proof of the VPN Tree Routing Conjecture on Ring Networks
Grandoni, F., Kaibel, V., Oriolo, G., Skutella, M.
Article in Oper. Res. Lett.
Packing and Partitioning Orbitopes
Kaibel, V., Pfetsch, M. E.
Article in Math. Program.
2007
Two New Bounds for the Random-Edge Simplex-Algorithm
Gärtner, B., Kaibel, V.
SIAM J. Disc. Math.
Orbitopal Fixing
Kaibel, V., Peinhardt, M., Pfetsch, M. E.
Appeared in Integer Programming and Combinatorial Optimization. Proceedings of IPCOP XII, Ithaca, NY
2006
Revlex-initial 0/1-polytopes
Gillmann, R., Kaibel, V.
Article in J. Combin. Theory Ser. A
LP-Based Local Approximation for Markov Decision Problems
Heinz, S., Kaibel, V., Peinhardt, M., Rambau, J., Tuchscherer, A.
Mathematik für den Volkssport
Kaibel, V., Koch, T.
On the Bottleneck Shortest Path Problem
Kaibel, V., Peinhardt, M.
2004
On the Expansion of Graphs of 0/1-Polytopes
Kaibel, V.
Chapter in The Sharpest Cut: The Impact of Manfred Padberg and His Work
Low-Dimensional Faces of Random 0/1-Polytopes
Kaibel, V.
Appeard in Integer Programming and Combinatorial Optimization. Proceedings of IPCO X, New York, NY
The Simplex Algorithm in Dimension Three
Kaibel, V., Mechtel, R., Sharir, M., Ziegler, G. M.
Article in SIAM J. Comput.
2003
Rotation Planning for the Continental Service of a European Airline
Elf, M., Jünger, M., Kaibel, V.
Chapter in Mathematics – Key Technologies for the Future. Joint Projects between Universities and Industry
Some Algorithmic Problems in Polytope Theory
Kaibel, V., Pfetsch, M. E.
Chapter in Algebra, Geometry, and Software Systems
On the Graph-Density of Random 0/1-Polytopes
Kaibel, V., Remshagen, A.
Appeared in Approximation, Randomization, and Combinatorial Optimization (Proc. RANDOM03)
On the Complexity of Polytope Isomorphism Problems
Kaibel, V., Schwartz, A.
Article in Graphs Comb.
Automorphism Groups of Cyclic Polytopes
Kaibel, V., Wassmer, A.
Counting Lattice Triangulations
Kaibel, V., Ziegler, G. M.
Chapter in Surveys in Combinatorics 2003
2002
On the k-Systems of a Simple Polytope
Joswig, M., Körner, F., Kaibel, V.
Article in Isr. J. Math.
Reconstructing a Simple Polytope from its Graph
Kaibel, V.
Chapter in Combinatorial optimization – Eureka, You Shrink!
Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences
Kaibel, V., Pfetsch, M. E.
Article in Comput. Geom.
2001
Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes
Fleiner, T., Kaibel, V., Rote, G.
Article in European J. Comb.
Vertex-Facet Incidences of Unbounded Polyhedra
Joswig, M., Kaibel, V., Pfetsch, M. E., Ziegler, G. M.
Article in Adv. Geom.
On the SQAP-Polytope
Jünger, M., Kaibel, V.
Article in SIAM J. Opt.
The QAP-Polytope and the Star-Transformation
Jünger, M., Kaibel, V.
Article in Discr. Appl. Math.
Box-Inequalities for Quadratic Assignment Polytopes
Jünger, M., Kaibel, V.
Article in Math. Program. Ser. A
Zum Geburtstag ein Weltrekord
Kaibel, V.
Simple 0/1-Polytopes
Kaibel, V., Wolff, M.
Article in European J. Comb.
2000
Polyhedral Methods for the QAP
Kaibel, V.
Chapter in Nonlinear Assignment Problems: Algorithms and Applications
1999
Randomized Simplex Algorithms and Random Cubes
Joswig, M., Kaibel, V.
1998
Polyhedral Combinatorics of QAPs with Less Objects than Locations
Kaibel, V.
Appeared in Proceedings of the 6th International IPCO Conference, Houston, Texas
1997
Abstract Objective Function Graphs on the 3-Cube - A Classification by Realizability
Gärtner, B., Kaibel, V.
Polyhedral Combinatorics of the Quadratic Assignment Problem
Kaibel, V.
Ph.D. thesis at Universität zu Köln
1993
A Practical Method for Computing Correct Delaunay Triangulations in the Euclidian Metric
Jünger, M., Kaibel, V., Thienel, S.
Computing Delaunay-Triangulations in Manhattan and Maximum Metric
Jünger, M., Kaibel, V., Thienel, S.
Delaunay-Triangulierungen in verschiedenen Metriken
Kaibel, V.
Master's thesis at Universität zu Köln
Current projects
Mathematical Complexity Reduction
Duration: 01.04.2017 bis 31.03.2026
In the context of the proposed RTG we understand complexity as an intrinsic property that makes
it difficult to determine an appropriate mathematical representation of a real world problem, to assess the fundamental structures and properties of mathematical objects, and to algorithmically solve a given mathematical problem. By complexity reduction we refer to all approaches that help to overcome these difficulties in a systematic way and to achieve the aforementioned goals more efficiently.
For many mathematical tasks, approximation and dimension reduction are the most important tools to obtain
a simpler representation and computational speedups. We see complexity reduction in a more general way and
will also, e.g., investigate liftings to higher-dimensional spaces and consider the costs of data observation.
Our research goals are the development of cross-disciplinary mathematical theory and methods for complexity
reduction and the identification of relevant problem classes and effective exploitation of their structures.
We aim at a comprehensive teaching and research program based on geometric, algebraic, stochastic, and
analytic approaches, complemented by efficient numerical and computational implementations. In order to
ensure the success of our doctoral students, they will participate in a tailored structured study program. It will
contain training units in form of compact courses and weekly seminars, and encourage early integration into the
scientific community and networking. We expect that the RTG will also serve as a catalyst for a dissemination
of these successful practices within the Faculty of Mathematics and improve the gender situation.
Complexity reduction is a fundamental aspect of the scientific backgrounds of the principal investigators.
The combination of expertise from different areas of mathematics gives the RTG a unique profile, with high
chances for scientific breakthroughs. The RTG will be linked to two faculties, a Max Planck Institute, and
several national and international research activities in different scientific communities.
The students of the RTG will be trained to become proficient in a breadth of mathematical methods, and
thus be ready to cope with challenging tasks in particular in cross-disciplinary research teams. We expect an
impact both in terms of research successes, and in the education of the next generation of leading scientists in
academia and industry.
Completed projects
Mathematisches Komplexitätsreduktion (GRK 2297/1)
Duration: 01.04.2017 bis 30.09.2021
Das Projekt wird von den genannten Principal Investigators getragen. Diese sind den Instituten für Mathematische Optimierung (Averkov, Kaibel, Sager), für Algebra und Geometrie (Kahle, Nill, Pott), für Mathematische Stochastik (Kirch, Schwabe) und für Analysis und Numerik (Benner) der Fakultät zugeordnet. Benner ist zudem Direktor des Max-Planck Institutes für Dynamik komplexer technischer Systeme. Die Fakultät für Elektrotechnik und Informationstechnik ist über Findeisen beteiligt.
Im Kontext des vorgeschlagenen Graduiertenkollegs (GK) verstehen wir Komplexität als eine intrinsische Eigenschaft, die einen mathematischen Zugang zu einem Problem auf drei Ebenen erschwert. Diese Ebenen sind eine angemessene mathematische Darstellung eines realen Problems, die Erkenntnis fundamentaler Eigenschaften und Strukturen mathematischer Objekte und das algorithmische Lösen einer mathematischen Problemstellung. Wir bezeichnen alle Ansätze, die systematisch auf einer dieser drei Ebenen zu einer zumindest partiellen Verbesserung führen, als mathematische Komplexitätsreduktion.
Für viele mathematische Fragestellungen sind Approximation und Dimensionsreduktion die wichtigsten Werkzeuge auf dem Weg zu einer vereinfachten Darstellung und Rechenzeitgewinnen. Wir sehen die Komplexitätsreduktionin einem allgemeineren Sinne und werden zusätzlich auch Liftings in höherdimensionale Räume und den Einfluss der Kosten von Datenerhebungen systematisch untersuchen. Unsere Forschungsziele sind die Entwicklung von mathematischer Theorie und Algorithmen sowie die Identifikation relevanter Problemklassen und möglicher Strukturausnutzung im Fokus der oben beschriebenen Komplexitätsreduktion.
Unsere Vision ist ein umfassendes Lehr- und Forschungsprogramm, das auf geometrischen, algebraischen, stochastischen und analytischen Ansätzen beruht und durch effiziente numerische Implementierungen komplementiert wird. Die Doktorandinnen und Doktoranden werden an einem maßgeschneiderten Ausbildungsprogramm teilnehmen. Dieses enthält unter anderem Kompaktkurse, ein wöchentliches Seminar und ermutigt zu einer frühzeitigen Integration in die wissenschaftliche Community. Wir erwarten, dass das GK als ein Katalysator zur Etablierung dieser erfolgreichen DFG-Ausbildungskonzepte an der Fakultät für Mathematik dienen und zudem helfen wird, die Gleichstellungssituation zu verbessern.
Die Komplexitätsreduktion ist ein elementarer Aspekt der wissenschaftlichen Hintergründe der beteiligten Wissenschaftler. Die Kombination von Expertisen unterschiedlicher mathematischer Bereiche gibt dem GK ein Alleinstellungsmerkmal mit großen Chancen für wissenschaftliche Durchbrüche. Das GK wird Anknüpfungspunkte an zwei Fakultäten der OVGU, an ein Max Planck Institut und mehrere nationale und internationale Forschungsaktivitäten in verschiedenen wissenschaftlichen Communities haben. Die Studierenden im GK werden in einer Fülle von mathematischen Methoden und Konzepten ausgebildet und erlangen dadurch die Fähigkeit, herausfordernde Aufgaben zu lösen. Wir erwarten Erfolge in der Forschung und in der Ausbildung der nächsten Generation führender Wissenschaftler in Akademia und Industrie.
Erweiterte Formulierungen in der Kombinatorischen Optimierung
Duration: 01.10.2014 bis 31.12.2018
Die meisten für die kombinatorische Optimierung relevanten Polytope haben exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Das Konzept der erweiterten Formulierungen erlaubt es, Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder darzustellen. Das Ziel dieses Projekts ist, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen signifikant zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln.
Erweiterte Formulierungen in der Kombinatorischen Optimierung
Duration: 01.10.2012 bis 30.09.2013
Die meisten für die kombinatorische Optimierung relevanten Polytope haben exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Das Konzept der erweiterten Formulierungen erlaubt es, Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder darzustellen. Das Ziel dieses Projekts ist, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen signifikant zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln.
Polyedrische Kombinatorik der Symmetriebrechung in der Ganzzahligen Linearen Optimierung
Duration: 01.05.2009 bis 30.04.2012
Im Rahmen dieses Projektes werden grundlegende Fragen zu Symmetrien in der Ganzzahligen Linearen Optimierung untersucht. Insbesondere geht es dabei um die Beschreibung und Analyse von Polytopen, die Symmetrien beschreiben. Optimierungsprobleme, deren Lösungen Symmetrien aufweisen, führen in der Praxis häufig zu Problemen, da sie schlechte Schranken und ein schlechtes Enumerationsverhalten aufweisen. Ein besseres Verständnis der Polytope, die diesem Phänomen zu Grunde liegen, soll daher zu einer besseren Lesbarkeit dieser Probleme führen.
Erweiterte Formulierungen in der Kombinatorischen Optimierung
Duration: 01.01.2010 bis 31.12.2011
Für viele kombinatorische Optimierungsprobleme sind die Beschreibungen der in natürlicher Weise zugeordneten Polytope notwendigerweise sehr kompliziert und groß. In machen Fällen kann man jedoch diese komlizierten Polytope als lineare Projektionen einfach zu beschreibender höher dimensionaler Polyeder darstellen und mit diesen Darstellungen in der gleichen Weise Theorie und Praxis der Linearen Optimierung für das vorliegende kombinatorische Optimierungsproblem nutzbar machen. In diesem Projekt leiten wir zum einen Methoden zum Aufstellen solcher erweiterter Formulierungen her und untersuchen zum andern, welche grundsätzlichen Grenzen dieser Methodik gesetzt sind.
Grundlegende Untersuchungen zu Orbitopen
Duration: 01.01.2010 bis 31.12.2010
Orbitope sind Polyeder, die erfolgreich zur Ausnutzung von speziellen Symmetrien in ganzzahligen linearen Optimierungsproblemen benutzt werden. In diesem Projekt untersuchen wir grundlegende Fragen zu Orbitopen, also zu konvexen Hüllen von 0/1-Matrizen, die lexikographisch maximal in ihrem Orbit unter einer durch Spaltenpermutation operierenden Gruppe sind. Ziel des Projekts ist es, heraus zu finden, welche Einschränkungen an die 0/1-Matrizen die Orbitope so kompliziert werden lassen, dass man unter komplexitätstheoretischen Annahmen keine brauchbaren Beschreibungen erwarten kann, und andererseits für Klassen, bei denen dies nicht der Fall ist, Ungleichungsbeschreibungen herzuleiten.
Symmetrie und Dynamik in der gemischt-ganzzahligen Optimierung für biologische Anwendungen
Duration: 15.05.2008 bis 14.05.2009
Die Einführung von zeitindizierten Variablen in der gemischt-ganzzahligen Optimierung zur Abbildung zeitlicher Dynamik wie zum Beispiel in biologischen Signal-Netzwerken führt zu Modellen, für deren effiziente Lösung eine spezielle Analyse der mathematischen Struktur erforderlich ist. Dabei muss in besonderer Weise die durch die Zeitindizierung in das Modell importierte Symmetrie untersucht und ausgenutzt werden. In diesem Projekt sollen zum Einen für die Symmetriebrechung in der ganzzahligen linearen Optimierung grundlegende Polytope untersucht werden und zum anderen anhand von Modellen für Signal-Netzwerke spezifische Verfahren zur Symmetrie-Ausnutzung in dynamischen gemischt-ganzzahligen Optimierungsproblemen entwickelt werden.
Enummeration und zufälliges Erzeugen
Duration: 01.02.2007 bis 31.01.2008
Teilprojekt der DFG-Forschergruppe "Algorithmen, Struktur, Zufall", in der außerdem Projekte der Arbeitgruppen von Prof. Dr. Günter Ziegler (TU Berlin), Prof. Dr. Martin Grötschel (Zuse-Institut Berlin) und Prof. Dr. Hans-Jürgen Prömel (HU Berlin) gefördert werden. In diesem letzten Jahr der Förderperiode werden insbesondere Beispiele untersucht, die eine Vermutung von Mihail und Vazirani über die Expansionseigenschaften der Graphen von 0/1-Polytopen unterstützen. Ein Beweis dieser Vermutung hätte weitreichende Folgen für das algorithmische Zählen komplexer kombinatorischer Objekte.
Symmetrien in der Ganzzahligen Linearen Optimierung
Duration: 01.07.2006 bis 31.12.2007
Ganzzahlige Lineare Modelle werden für eine Vielzahl von Optimierungsproblemen verwendet. Häufig weisen diese Modelle eine hohe ymmetrie auf, die dazu führt, dass Algorithmen unnötig viel Arbeit verrichten müssen. In diesem Projekt untersuchen wir Möglichkeiten, solche Symmetrien zu brechen und damit die Effizienz von Algorithmen für die zu lösenden Optimierungsprobleme deutlich zu steigern.
Since 2007 | Professor (W3) for Mathematical Optimization at Otto-von-Guericke Universität Magdeburg |
2006 | Visiting Professor at TU Berlin |
2003-2006 | Privatdozent at TU Berlin |
2005-2006 | Deputy head of the Department for Optimization at Zuse-Institute Berlin (ZIB) |
2003-2004 | Head of the Junior Research Group Optimization at the DFG Research Center MATHEON, Berlin |
2003-2004 | Member of the Executive Board of the DFG Research Center MATHEON, Berlin |
2005-2006 | Scientist in Charge for Application Area B Logistics, Traffic and Telecommunication Networks of the DFG Research Center MATHEON, Berlin |
2003 | Visitor at the Mathematical Sciences Research Institute (MSRI), Berkeley (October-November) |
1999-2003 | Researcher (Wissenschaftlicher Mitarbeiter) at TU Berlin (with Günter M. Ziegler) |
2002 | Habilitation (Mathematics) at TU Berlin |
1993-1999 | Researcher (Wissenschaftlicher Mitarbeiter) at Universität zu Köln (with Michael Jünger) |
1997 | Doctoral Degree (Dr. rer. nat.) at Universität zu Köln (Supervisor: Michael Jünger, Thesis: Polyhedral Combinatorics of the Quadratic Assignment Problem) |
1993 | Diploma (Mathematics) at Universität zu Köln (Supervisor: Michael Jünger, Thesis: Delaunay-Triangulierungen in verschiedenen Metriken) |
1989-1993 | Student of Mathematics and Computer Science, Universität zu Köln |
- Mathematics M1 (Lecture) ( Link zur LV im LSF )
- Mathematik M1 (VL) ( Link zur LV im LSF )
- Oberseminar Mathematische Optimierung ( Link zur LV im LSF )
Office hours thursdays 11-12 a.m. (in the office or via Zoom)