Publications

2017

  • A Note on Matchings Constructed during Edmonds' Weighted Perfect
    Volker Kaibel, Matthias Walter
    In: arXiv:1703.09505, 2017 (pdf, bibtex)

2016

  • Maximum Semidefinite and Linear Extension Complexity of Families of Polytopes
    Gennadiy Averkov, Voker Kaibel, Stefan Weltge
    In: To appear in Math. Program., Ser. A (DOI 10.1007/s10107-017-1134-7), 2016 (pdf, bibtex)
  • Extended Formulations for Independence Polytopes of Regular Matroids
    Kaibel, Volker, Lee, Jon, Walter, Matthias, Weltge, Stefan
    In: Graphs and Combinatorics, 2016, 32 (5), 1931--1944 (pdf, bibtex)

2015

  • Subgraph polytopes and independence polytopes of count matroids
    Michele Conforti, Volker Kaibel, Matthias Walter, Stefan Weltge
    In: Operations Research Letters, 2015, 43 (5), 457 - 460 (pdf, bibtex)
  • The Unimodular Intersection Problem
    Volker Kaibel, Shmuel Onn, Pauline Sarrabezolles
    In: Operations Research Letters, 2015, 43 (pdf, bibtex)
  • A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
    Volker Kaibel, Stefan Weltge
    In: Discrete & Computational Geometry, 2015, 53 (2), 396--401 (pdf, bibtex)
  • Simple extensions of polytopes
    Volker Kaibel, Matthias Walter
    In: Math. Program. Ser. B, 2015, 154 (1-2), 381-406 (pdf, bibtex)
  • Lower Bounds on the Sizes of Integer Programs without Additional Variables
    Volker Kaibel, Stefan Weltge
    In: Math. Program. Ser. B, 2015, 154 (1-2), 407--425 (pdf, bibtex)
  • Forbidden Vertices
    Gustavo Angulo, Shabbir Ahmed, Santanu S. Dey, Volker Kaibel
    In: Mathematics of Oper. Res., 2015, 40 (2), 350-360 (pdf, bibtex)

2014

  • Simple Extensions of Polytopes
    Volker Kaibel, Matthias Walter
    In: Integer Programming and Combinatorial Optimization, 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, Jon Lee, Jens Vygen (eds.), Lecture Notes in Computer Science 8494, Springer, 2014, 309--320 (pdf, bibtex)
  • Lower Bounds on the Sizes of Integer Programs without Additional Variables
    Volker Kaibel, Stefan Weltge
    In: Integer Programming and Combinatorial Optimization, 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, Jon Lee, Jens Vygen (eds.), Lecture Notes in Computer Science 8494, Springer, 2014, 321--332 (bibtex)

2013

  • Which Nonnegative Matrices Are Slack Matrices?
    Joao Gouveia, Roland Grappe, Volker Kaibel, Kanstantsin Pashkovich, Richard Z. Robinson, Rekha R. Thomas
    In: Linear Algebra Appl., 2013, 2921--2933 (pdf, bibtex)
  • Constructing Extended Formulations from Reflection Relations
    Volker Kaibel, Kanstantsin Pashkovich
    In: Facets of Combinatorial Optimization -- Festschrift for Martin Grötschel, Springer Berlin Heidelberg, 2013, 77-100 (bibtex)
  • Combinatorial Bounds on Nonnegative Rank and Extended Formulations
    Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
    In: Discrete Math., 2013, 313 (1), 67-83 (pdf, bibtex)

2012

  • Symmetry Matters for Sizes of Extended Formulations
    Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
    In: SIAM J. Disc. Math., 2012, 26 (3), 1361--1382 (pdf, bibtex)

2011

  • Orbitopal fixing
    Volker Kaibel, Matthias Peinhardt, Marc E. Pfetsch
    In: Discr. Opt., 2011, 8 (4), 595--610 (pdf, bibtex)
  • Constructing Extended Formulations from Reflection Relations
    Volker Kaibel, Kanstantsin Pashkovich
    In: Integer Programming and Combinatorial Optimization. Proceedings of IPCO XV, New York, NY, O. Günlük, G. Woeginger (eds.), Lecture Notes in Computer Science 6655, Springer, 2011, 287--300 (pdf, bibtex)
  • Extended Formulations in Combinatorial Optimization
    Volker Kaibel
    In: Optima 85, 2011 (pdf, bibtex)
  • Basic Polyhedral Theory
    Volker Kaibel
    In: Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2011 (pdf, bibtex)
  • Finding Descriptions of Polytopes via Extended Formulations and Liftings
    Volker Kaibel, Andreas Loos
    In: Progress in Combinatorial Optimization, Wiley, 2011 (pdf, bibtex)

2010

  • On cardinality constrained cycle and path polytopes
    Volker Kaibel, Rüdiger Stephan
    In: Math. Program., 2010, 123 (2, Ser. A), 371--394 (pdf, bibtex)
  • Branched Polyhedral Systems
    Volker Kaibel, Andreas Loos
    In: Integer Programming and Combinatorial Optimization. Proceedings of IPCO XIV, Ithaca, NY, Friedrich Eisenbrand, Bruce F. Shepherd (eds.), Lecture Notes in Computer Science 6080, Springer, 2010, 177--190 (pdf, bibtex)
  • Symmetry Matters for the Sizes of Extended Formulations
    Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
    In: Integer Programming and Combinatorial Optimization. Proceedings of IPCO XIV, Ithaca, NY, Friedrich Eisenbrand, Bruce F. Shepherd (eds.), Lecture Notes in Computer Science 6080, Springer, 2010, 135--148 (pdf, bibtex)

2009

  • Another Proof of the Fact that Polyhedral Cones are Finitely Generated
    Volker Kaibel
    In: arXiv:0912.2927v1, 2009 (pdf, bibtex)
  • Two Theorems on Projections of Polyhedra
    Volker Kaibel
    2009 (pdf, bibtex)
  • Extended Formulations for Packing and Partitioning Orbitopes
    Yuri Faenza, Volker Kaibel
    In: Math. Oper. Res., 2009, 34 (3), 686--697 (pdf, bibtex)

2008

  • Packing and Partitioning Orbitopes
    Volker Kaibel, Marc E. Pfetsch
    In: Math. Program., 2008, 114 (1, Ser. A), 1--36 (pdf, bibtex)
  • A Short Proof of the VPN Tree Routing Conjecture on Ring Networks
    Fabrizio Grandoni, Kaibel, Volker, Gianpaolo Oriolo, Martin Skutella
    In: Oper. Res. Lett., 2008, 36 (3), 361--365 (pdf, bibtex)

2007

  • Orbitopal Fixing
    Volker Kaibel, Matthias Peinhardt, Marc E. Pfetsch
    In: Integer Programming and Combinatorial Optimization. Proceedings of IPCOP XII, Ithaca, NY, Matteo Fischetti, David P. Williamson (eds.), Lecture Notes in Computer Science 4315, Springer, 2007, 74--88 (pdf, bibtex)
  • Special issue on IPCO 2005
    Michael Jünger, Volker Kaibel
    In: Math. Program., 2007, 110 (1), 1--2 (bibtex)
  • Two New Bounds for the Random-Edge Simplex-Algorithm
    Bernd Gärtner, Volker Kaibel
    In: SIAM J. Disc. Math., 2007, 21 (1), 178--190 (electronic) (pdf, bibtex)

2006

  • Revlex-initial $0/1$-polytopes
    Rafael Gillmann, Volker Kaibel
    In: J. Combin. Theory Ser. A, 2006, 113 (5), 799--821 (pdf, bibtex)
  • Mathematik für den Volkssport
    Volker Kaibel, Thorsten Koch
    In: DMV-Mitteilungen II/06, 93--96, 2006 (pdf, bibtex)
  • On the Bottleneck Shortest Path Problem
    Volker Kaibel, Matthias Peinhardt
    ZIB-Report 06-22, Zuse Institute Berlin, 2006 (pdf, bibtex)
  • LP-Based Local Approximation for Markov Decision Problems
    Stefan Heinz, Volker Kaibel, Matthias Peinhardt, Jörg Rambau, Andreas Tuchscherer
    ZIB-Report 06-20, Zuse Intitute Berlin, 2006 (pdf, bibtex)

2005

  • Integer Programming and Combinatorial Optimization, 11th International Conference, IPCO 2005, Berlin, Germany, June 8-10, 2005. Proceedings
    proceedings (bibtex)

2004

  • On the Expansion of Graphs of 0/1-Polytopes
    Volker Kaibel
    In: The Sharpest Cut: The Impact of Manfred Padberg and His Work, SIAM, 2004, 4, 199--216 (pdf, bibtex)
  • The Simplex Algorithm in Dimension Three
    Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler
    In: SIAM J. Comput., 2004, 34 (2), 475--497 (electronic) (pdf, bibtex)
  • Low-Dimensional Faces of Random $0/1$-Polytopes
    Volker Kaibel
    In: Integer Programming and Combinatorial Optimization. Proceedings of IPCO X, New York, NY, Daniel Bienstock, George Nemhauser (eds.), Lecture Notes in Computer Science 3064, Springer, 2004, 401--415 (pdf, bibtex)

2003

  • Some Algorithmic Problems in Polytope Theory
    Volker Kaibel, Marc E. Pfetsch
    In: Algebra, Geometry, and Software Systems, Springer, 2003, 23--47 (pdf, bibtex)
  • Rotation Planning for the Continental Service of a European Airline
    Matthias Elf, Michael Jünger, Volker Kaibel
    In: Mathematics -- Key Technologies for the Future. Joint Projects between Universities and Industry, Springer, 2003, 675--689 (pdf, bibtex)
  • Convex Polytopes
    Branko Grünbaum
    Volker Kaibel, Victor Klee, Günter M. Ziegler (eds.)
    Preparation of the 2nd edition, including new pages on the development of polytope theory between 1967 and 2002
    Volume 221 of Graduate Texts in Mathematics, Springer, 2003 (bibtex)
  • Automorphism Groups of Cyclic Polytopes
    Volker Kaibel, Arnold Wassmer
    2003 (pdf, bibtex)
  • On the Complexity of Polytope Isomorphism Problems
    Volker Kaibel, Alexander Schwartz
    In: Graphs Comb., 2003, 19 (2), 215--230 (pdf, bibtex)
  • Counting Lattice Triangulations
    Volker Kaibel, Günter M. Ziegler
    In: Surveys in Combinatorics 2003, Cambridge University Press, 2003, 307, 277--307 (pdf, bibtex)
  • On the Graph-Density of Random 0/1-Polytopes
    Volker Kaibel, Anja Remshagen
    In: Approximation, Randomization, and Combinatorial Optimization (Proc. RANDOM03), Sanjeev Arora, Klaus Jansen, Jose D.P. Rolim, Amit Sahai (eds.), Lecture Notes in Computer Science 2764, Springer, 2003, 318--328 (pdf, bibtex)

2002

  • Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences
    Volker Kaibel, Marc E. Pfetsch
    In: Comput. Geom., 2002, 23, 281--290 (pdf, bibtex)
  • On the k-Systems of a Simple Polytope
    Michael Joswig, Friederike Körner, Volker Kaibel
    In: Isr. J. Math., 2002, 129, 109--118 (pdf, bibtex)
  • Reconstructing a Simple Polytope from its Graph
    Volker Kaibel
    In: Combinatorial optimization -- Eureka, You Shrink!, Springer, 2002, 2570, 105--118 (pdf, bibtex)

2001

  • Simple 0/1-Polytopes
    Volker Kaibel, Martin Wolff
    In: European J. Comb., 2001, 21 (1), 139--144 (pdf, bibtex)
  • Vertex-Facet Incidences of Unbounded Polyhedra
    Michael Joswig, Volker Kaibel, Marc E. Pfetsch, Günter M. Ziegler
    In: Adv. Geom., 2001, 1 (1), 23--36 (pdf, bibtex)
  • The QAP-Polytope and the Star-Transformation
    Michael Jünger, Volker Kaibel
    In: Discr. Appl. Math., 2001, 111 (3), 283--306 (pdf, bibtex)
  • Box-Inequalities for Quadratic Assignment Polytopes
    Michael Jünger, Volker Kaibel
    In: Math. Program. Ser. A, 2001, 91, 175--197 (pdf, bibtex)
  • On the SQAP-Polytope
    Michael Jünger, Volker Kaibel
    In: SIAM J. Opt., 2001, 11 (2), 444--468 (pdf, bibtex)
  • Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes
    Tamas Fleiner, Volker Kaibel, Günter Rote
    In: European J. Comb., 2001, 21 (1), 121--130 (pdf, bibtex)
  • Zum Geburtstag ein Weltrekord
    Volker Kaibel
    In: DMV-Mitteilungen IV/01, 16--18, 2001 (pdf, bibtex)

2000

  • Polyhedral Methods for the QAP
    Volker Kaibel
    In: Nonlinear Assignment Problems: Algorithms and Applications, Kluwer Academic Publishers, 2000, 109--141 (pdf, bibtex)

1999

  • Randomized Simplex Algorithms and Random Cubes
    Michael Joswig, Volker Kaibel
    TU Berlin, 1999 (pdf, bibtex)

1998

  • Polyhedral Combinatorics of QAPs with Less Objects than Locations
    Volker Kaibel
    In: Proceedings of the 6th International IPCO Conference, Houston, Texas, Robert E. Bixby, Andrew E. Boyd, Roger Z. Rios-Mercado (eds.), Lecture Notes in Computer Science 1412, Springer, 1998, 409--422 (pdf, bibtex)

1997

  • Abstract Objective Function Graphs on the 3-Cube - A Classification by Realizability
    Bernd Gärtner, Volker Kaibel
    TU Berlin, 1997 (pdf, bibtex)
  • Polyhedral Combinatorics of the Quadratic Assignment Problem
    Volker Kaibel
    Doctoral Dissertation, Universität zu Köln, 1997 (pdf, bibtex)

1993

  • A Practical Method for Computing Correct Delaunay Triangulations in the Euclidian Metric
    Michael Jünger, Volker Kaibel, Stefan Thienel
    Universität zu Köln, 1993 (pdf, bibtex)
  • Delaunay-Triangulierungen in verschiedenen Metriken
    Volker Kaibel
    Diploma Thesis, Universität zu Köln, 1993 (pdf, bibtex)
  • Computing Delaunay-Triangulations in Manhattan and Maximum Metric
    Michael Jünger, Volker Kaibel, Stefan Thienel
    Universität zu Köln, 1993 (pdf, bibtex)
Volker Kaibel
Chair for Mathematical Optimization