Prof. Ph. D. Mathias Schacht

• FG 413: Algorithmen III (-5)

  Quelle ↗

  <p>Für eine Reihe bekannter kominatorischer Optimierungsprobleme, z.B. Graphenfärbung, das Stabile-Menge-Problem in Graphen oder das MAX k-SAT-Problem, sind Nichtapproximierbarkeitsresultate bekannt. Unter gewissen komplexitätstheoretischen Annahmen lassen diese Probleme also keine polynomiellen Algorithmen zu, die auf jeder Instanz eine optimale Lösung bzw. eine gute Approximationslösung berechnen. Daher fragte bereits Karp nach (a) Heuristiken, die auf fast jeder Instanz I eine gute Lösung des Optimierungsproblems bestimmen, und auf jeder Eingabe polynomielle Laufzeit haben, sowie nach (b) Algorithmen mit erwartet polynomieller Laufzeit, die auf jeder Eingabe eine akzeptable Approximationsgüte garantieren und deren erwartete Laufzeit polynomiell ist,und gab damit den Anstoß zur probabilistischen Analyse von Algorithmen. Im Sinne von Analyse von Algorithmen bei zufälliger Eingabe befassen wir uns in diesem Projekt mit fundamentalen kombinatorischen Problemen wie Graphenfärbung, Finden einer größten stabilen Menge oder dem Erfüllbarkeitsproblem.</p> <p>Neben der probabilistischen Analyse soll in diesem Projekt der Zufall auch als algorithmisches Konzept studiert werden. Dann lautet die Zielsetzung, durch Randomisierung verbesserte Algorithmen zu entwickeln.</p>

• FG 413: Algorithmen III (-Z)

  Quelle ↗

  <p>Der Entwurf und die Analyse von Algorithmen ist eng verknüpft mit Einsichten in die Struktur der Objekte, die die Algorithmen als Eingabe erhalten. Das zentrale Thema des Forschungsvorhabens ist es, diese Verknüpfung im Hinblick auf den Einfluss des Zufalls zu untersuchen - wie wirkt sich die Hinzunahme von Zufall auf algorithmische und strukturelle Fragestellungen in der Diskreten Mathematik aus?</p> <p>Der Zufall ist hierbei gleichermaßen Forschungsobjekt wie Untersuchungsmethode. Im Hinblick auf Strukturerkenntnisse wird einerseits nach Eigenschaften gesucht, die zufällige Objekte mit hoher Wahrscheinlichkeit besitzen, andererseits charakterisieren wir Objekte durch Benutzung des Zufalls. Und auch unter algorithmischen Aspekten setzt sich diese Dualität fort: Einerseits wird untersucht, wie sich Algorithmen auf zufälligen Eingaben verhalten, andererseits werden Verfahren analysiert, deren Entscheidungen zufällige Komponenten aufweisen.</p> <p>Auf der algorithmischen Seite gilt das Interesse kombinatorischen Optimierungsproblemen. Dadurch treten ganz natürlich Polytope, Graphen und partielle Ordnungen als Forschungsobjekte von Strukturuntersuchungen in den Mittelpunkt. Die Forschergruppe bündelt dabei die individuellen Erfahrungen und Kompetenzen, die die beteiligten Arbeitsgruppen in den letzten Jahren mit unterschiedlichen Ansätzen in dem Spannungsfeld von Algorithmen, Struktur und Zufall gewonnen haben.</p>

• The Regularity Method for Sparse Graphs and Hypergraphs

  Quelle ↗

  The Regularity Lemma of E. Szemeredi for graphs asserts that every dense graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type. This observation is called Counting Lemma. The interplay of Szemeredi's Regularity Lemma and the Counting Lemma has had a series of successes in Discrete Mathematics. In recent years the Regularity Method was partly expanded to new types of discrete structures: sparse graphs and k-uniform hypergraphs. In particular, analogues of the Regularity Lemma for these combinatorial objects were established. In the proposed program, we seek a deeper understanding of the random-like behavior guaranteed by those Regularity Lemmas. Furthermore, we focus on applications of these novel techniques in the area of extremal combinatorics.

Noch keine Publikationen aus OpenAlex zugeordnet.