TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 23161

Pushing the Limits of Computational Combinatorial Constructions

( 16. Apr – 21. Apr, 2023 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/23161

Organisatoren

Kontakt

Gemeinsame Dokumente


Programm

Summary

Objectives of the seminar

In this Dagstuhl Seminar, the focus was on computational methods for challenging problems in combinatorial construction. This seminar brought together researchers with different expertise: those with a deep understanding of combinatorial objects and experts in algorithm design and high-performance computing. Participants identified important problems for codes, graphs, and designs; and discussed state-of-the-art methods for challenging problems in constructing combinatorial objects. Additionally, the seminar brought together experts on combinatorial algorithms and representatives from different scientific communities developing practical techniques for attacking general hard problems, for example, in the framework of SAT solving, integer linear programming, and optimization.

General overview of the research topic

In discrete mathematics, construction and classification of structures are core problems. Computational methods have been essential in settling important mathematical questions, such as the proof of the four color theorem (Apel and Haken, 1976) and the nonexistence of projective planes of order 10 (Lam et al., 1989). Isomorph-free exhaustive searches are quite challenging with the number of nonequivalent objects often growing exponentially with the input size. For example, the classification of Steiner triple systems of order 19 (Kaski and Östergard, 2004) involved producing a list of more than 11 billion such objects. Vast exhaustive searches are also used to establish negative results, as in the non-existence of 16-clue Sudoku puzzles (McGuire et al., 2012), celebrated by the media due to its connection with the famous puzzle. Many of the central problems, even subproblems, are (NP-)hard, but with improved algorithms and general approaches, it is still possible to handle instances with not too small parameters.

Structure of the seminar

  • Curtis Bright (University of Windsor, CA): SAT + Isomorph-free Generation ...and the Quest for the Minimum Kochen–Specker System
  • Daniel Heinlein (Aalto University, FI): Enumerating Steiner Triple Systems: Counting STS(21)s
  • Vedran Krcadinac (University of Zagreb, HR): On higher-dimensional designs
  • Pascal Schweitzer (TU Darmstadt, DE): Automorphisms, Isomorphisms, and Canonization: recent developments

In the first two days of the seminar six leading experts gave 30 minute tutorials and provided input on the current limits of the area:

  • Brendan McKay (Australian National University - Acton, AU): SURGE : A fact open-source chemical graph generator
  • Gordon Royle (The University of Western Australia - Crawley, AU): Three stories about computational combinatorics
  • Manfred Scheucher (TU Berlin, DE): Using SAT Solvers in Combinatorics and Geometry
  • Brett Stevens (Carleton University - Ottawa, CA): Thoughts on Computational Design Theory
  • Leo Storme (Ghent University, BE): Computational methods in finite geometry
  • Ian M. Wanless (Monash University - Clayton, AU): Open problems on orthogonal(ish) arrays

In the remaining time participants were partitioned into five working groups, brainstorming and exchanging ideas:

  • Improving reliability and usability of computational projects
  • SAT working group
  • Isomorphism Solvers
  • Design theory working group
  • Tactical decompositions working group
Copyright Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Motivation

In discrete mathematics, construction and classification of structures are core problems. Computational methods have been essential in settling important mathematical questions, such as the proof of the four color theorem (Apel and Haken, 1976) and the nonexistence of projective planes of order 10 (Lam et al., 1989). Isomorph-free exhaustive searches are quite challenging with the number of nonequivalent objects often growing exponentially with the input size. For example, the classification of Steiner triple systems of order 19 (Kaski and Östergård, 2004) involved producing a list of more than 11 billion such objects. Vast exhaustive searches are also used to establish negative results, as in the non-existence of 16-clue Sudoku puzzles (McGuire et al., 2012), celebrated by the media due to its connection with the famous puzzle. Many of the central problems, even subproblems, are (NP-)hard, but with improved algorithms and general approaches, it is still possible to handle instances with not too small parameters.

In this Dagstuhl seminar, we will focus on computational methods for challenging problems in combinatorial construction . This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, and combinatorial optimization. There will be an emphasis on problems involving graphs, designs and codes , also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes. Examples of specific cases to consider are the existence problems for q-analogs of the Fano plane and projective planes with an order that is not a prime power.

This seminar aims to bring together researchers with different expertise: those with a deep understanding of combinatorial objects and experts in algorithms design and high-performance computing. Participants will discuss and work to improve on state-of-the-art methods for challenging problems in constructing combinatorial objects and highlight important open problems to attack. Additionally, the seminar aims to bring together experts on combinatorial algorithms and representatives from different scientific communities developing practical techniques for attacking general hard problems, for example, in the framework of satisfiability, integer linear programming, and optimization. The contribution of scholars working in high-performance computing and experts on relevant computer architectures (such as GPUs) will also be valuable. The goal of this seminar is to provide a creative impulse towards new research in the topic. All participants will get the chance to report on their experience, either in plenary short talks or in working group panels. Dealing with finite discrete problems, which can always be solved in finite time, success is about algorithms and computational resources. This venue will give opportunity to the researchers also to discuss the challenges found when they did not succeed, and it could be catalytic for advances in the field. A short-term goal of the seminar is to exchange information and initiate new collaborative research on the themes of the seminar. We hope the workshop will generate new ideas, new problems, new collaborations and new breakthroughs, with significant impact in the upcoming years.

Copyright Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Teilnehmer

Klassifikation
  • Data Structures and Algorithms
  • Discrete Mathematics
  • Mathematical Software

Schlagworte
  • combinatorial algorithms
  • subspace designs
  • finite geometries
  • automorphism groups