Geometrie und Algorithmen zur Ausnutzung Polyedrischer Symmetrien

• Antragsteller: Professor Dr. Achill Schürmann
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2015 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 263949937

• Erstellungsjahr: 2018

Zusammenfassung der Projektergebnisse

Main aim of this research project was to get a better understanding of polyhedral symmetries and making advancements in using them in practical polyhedral computations. The underlying long term vision being that symmetry-exploiting algorithms will become standard tools in polyhedral computations, so that they are used in mathematical software whenever symmetry is available. Any progress towards this goal has a significant long-term impact on diverse mathematical disciplines and applications, since polyhedral computations are widely used. During the course of this project, new theories for the better understanding of affine symmetry groups of polytopes have been developed. We have in particular answered when a given matrix group implies additional affine symmetries for any orbit polytope having it as its symmetry group. We have solved several difficult polyhedral representation conversion problems, with applications ranging from the classification of Dirichlet-Voronoi polyhedra of lattices to cohomology computations based on reduction theories of quadratic forms. For the study of symmetric integer linear programming problems, a new notion of normalizer equivalence has been introduced and studied. Reformulations based on it and other symmetry exploiting techniques have been shown to work on specific test instances. For the theory of lattice point counting we have introduced a new type of local formula, in which symmetries can be exploited. For several concrete computational problems in voting theory, we have used symmetry exploiting techniques. Subsuming, the project was very successful, also in some unexpected ways. For several specific problems, we successfully applied new symmetry exploiting techniques. However, a lot of further research will be necessary to turn symmetryexploiting algorithms into standard tools in polyhedral computations.

Projektbezogene Publikationen (Auswahl)

• Affine Symmetries of Orbit Polytopes, Adv. Math., 288 (2016), 386–425
  Erik Friese and Frieder Ladisch
  
• Realizations of abstract regular polytopes from a representation theoretic view Aequationes Math., 90 (2016), 1169–1193
  Frieder Ladisch
  
• The complete classification of five-dimensional Dirichlet-Voronoi polyhedra of translational lattices, Acta Crystallographica, A72 (2016), 673–683
  Mathieu Dutour Sikirić, Alexey Garber, Achill Schürmann, Clara Waldmann
  
• The impact of dependence among voters preferences with partial indifference, Quality & Quantity, 51 (2017), 2793–2812
  Erik Friese, William V. Gehrlein, Dominique Lepelley, Achill Schürmann
  
• A property of the Birkhoff polytope, Algebraic Combinatorics, 1 (2018), no. 2, p. 275–281
  Barbara Baumeister and Frieder Ladisch
  
• Equivalence of Lattice Orbit Polytopes, SIAM J. on Appl. Alg. Geom., 2 (2018), 259–280
  Frieder Ladisch and Achill Schürmann