http://www.dagstuhl.de/18281

08. – 13. Juli 2018, Dagstuhl Seminar 18281

Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices

Organisatoren

Jérémy Barbay (University of Chile – Santiago de Chile, CL)
Johannes Fischer (TU Dortmund, DE)
Stefan Kratsch (HU Berlin, DE)
Srinivasa Rao Satti (Seoul National University, KR)

Auskunft zu diesem Dagstuhl Seminar erteilen

Annette Beyer zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Motivation

This Dagstuhl Seminar will bring together researchers from the area of adaptive analysis of algorithms; the study of parameterized complexity of NP-hard problems; the area focused on compressed data structures; and the area concerned with the study of compressed indexes. While all of these subareas of algorithms and data structures, respectively, focus on ``going beyond the worst-case'' for classes of structurally restricted inputs, there has been a limited amount of interactions between them, with some results being "discovered" twice.

The goal of the seminar is to foster this interaction both during the seminar and in the future by:

  1. teaching one another the key techniques of one’s areas, through tutorials and short talks (with volunteers among the guests or organizers giving short tutorials on the very first day);
  2. discussing open problems at the intersection of the areas in varying small groups (guests will be invited to submit and present a list of results from their areas which they think could be applied to other areas); and
  3. compiling those techniques and open problems in a collective document realized in collaboration between volunteers among the participants (as proceedings of the seminar).

Examples of synergies include:

  1. techniques developed for sorting multisets and used to design compressed data structures supporting operators on permutations and functions (e.g. sorting algorithms and compression schemes taking advantage of existing subsequences of consecutive positions already sorted, or taking advantage of the potential imbalance between the frequencies of various elements of the input);
  2. techniques developed to study the parameterized complexity of graph algorithms which can be used to design compressed data structures for such graphs (e.g. max clique, max clique edit, etc.);
  3. the use of difficulty measures such as entropy for both running times and space usage (e.g. do instance optimal results on the running time yield any compression result?);
  4. studying which measures of compressibility of the data can also be applied to the analysis of the size of an index required in order to support additional operators on this data;
  5. techniques taking advantage at once of the input order, the input structure, the query order and the query structure; and others to be discovered during the seminar.

    License
      Creative Commons BY 3.0 DE
      Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

    Related Dagstuhl Seminar

    Classification

    • Data Structures / Algorithms / Complexity

    Keywords

    • Adaptive (analysis of) algorithms
    • Compressed data structures
    • Compressed indices
    • Parameterized complexity.

    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.