http://www.dagstuhl.de/16482

27. November – 02. Dezember 2016, Dagstuhl Seminar 16482

Algorithms and Effectivity in Tropical Mathematics and Beyond

Organisatoren

Stéphane Gaubert (INRIA Saclay – Île-de-France, FR)
Dima Grigoriev (Lille I University, FR)
Michael Joswig (TU Berlin, DE)
Thorsten Theobald (Goethe-Universität Frankfurt am Main, DE)


1 / 3 >

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 6, Issue 11 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente

Summary

Tropical mathematics is a uniting name for different research directions which involve the semi-ring of real numbers endowed with the operations min, + (called the tropical semi-ring). It has emerged in several areas of computer science and of pure and applied mathematics. For the first time, this seminar brought together the computer science and the mathematics viewpoints. A focus was on effective methods, algorithms and complexity bounds in tropical mathematics, and on their relations with open questions in various areas of computer science, including optimization, game theory and circuit complexity.

One of the oldest open algorithmic challenges in tropical mathematics is the complexity of solving systems of tropical linear equalities and inequalities. It is known to be equivalent to solving mean payoff games. The solvability of these problems is among the few known problems which are contained in the intersection NP cap co-NP, but not currently known to be in P. This leads to new approaches in linear programming or convex semialgebraic programming over nonarchimedean fields.

According to the organizers' points of view the seminar was quite successful. In addition to 28 talks there were many informal discussions and exchange of ideas in small groups. We expect several new common papers of the participants conceived during the seminar. An important feature was to bring together experts with different backgrounds who often knew other participants just by their publications. According to the opinions expressed, the participants learned a lot of new things. The seminar was especially useful for the young people.

Every talk, in addition to new results, also contained open problems. This created a lot of interaction in subsequent discussions. The audience was very active, many questions were posed to the speakers during the talks and the breaks.

  • Algorithmical problems of foundations of tropical mathematics (H. Markwig, D. Maclagan, F. Rincon, V. Podolskii);
  • Complexity of games and of tropical linear and convex algebra (M. Bodirsky, S. Gaubert, T. Hansen, M. Joswig, G. Loho, M. MacCaig, B. Schröter, S. Sergeev, M. Skomra);
  • Algorithms and complexity bounds on tropical varieties (F.Bihan, D. Grigoriev, S. Hampe, A. Jensen, T. Jörgens, L. Tabera, T. Theobald, T. de Wolff). We mention that S. Hampe has made a demonstration of the software Polymake for computations in tropical algebra;
  • Algorithms in tropical differential algebra (F. Aroca, C. Garay);
  • Interactions of tropical mathematics with algorithmic issues in classical mathematics (M. Akian, X. Allamigeon, Bo Lin, M. Rojas, C. Vinzant).

During the seminar a manuscript appeared (on the Internet) with the very strong claim of a quasi-polynomial complexity algorithm for parity games. It was a lucky coincidence that so many experts with various backgrounds were present. So a special evening session on Thursday was created to analyze this result and its ramifications. This was one more highlight.

License
  Creative Commons BY 3.0 Unported license
  Stéphane Gaubert, Dima Grigoriev, Michael Joswig, and Thorsten Theobald

Classification

  • Data Structures / Algorithms / Complexity
  • Optimization / Scheduling

Keywords

  • Algorithms in tropical mathematics
  • Complexity
  • Effective bounds
  • Optimization
  • Zero-sum games

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.