zum Inhalt springen

Kolloquium über Informatik

Termine Wintersemester 2020/2021

Der nächste Termin ist fett getdruckt. Abstracts befinden sich weiter unten auf dieser Seite.

Termin

Vortragende*r

Titel

6. November 2020

Stefan Zellmann (Universität zu Köln)

TBA

13. November 2020

Tim Oosterwijk (Universität Maastricht)

The Secretary Problem with Independent Sampling

20. November 2020

Bhaskar Ray Chaudhury (MPI Informatik, Saarbrücken)

TBA

27. November 2020

TBA

TBA

4. Dezember 2020

TBA

TBA

11. Dezember 2020

TBA

TBA

18. Dezember 2020

André Nusser (MPI Informatik, Saarbrücken)

TBA

8. Januar 2021

TBA

TBA

15. Januar 2021

TBA

TBA

22. Januar 2021

TBA

TBA

29. Januar 2021

TBA

TBA

5. Februar 2021

TBA

TBA

12. Februar 2021

TBA

TBA

 

Abstracts

 

6. November 2020: Stefan Zellmann (Universität zu Köln)

Titel: TBA

Abstract: TBA


13. November 2020: Tim Oosterwijk (Universität Maastricht)

Titel: The Secretary Problem with Independent Sampling

Abstract:

In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. In this talk we will consider both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we independently sample each element with a fixed probability p. The sampled elements become our information or history set and the game is played over the remaining elements.

In our upcoming SODA paper, we show how to obtain the best possible algorithms for both problems and all values of p. In this talk, I will mostly focus on the adversarial order case and show you the main ideas behind our proofs. This is joint work with José Correa, Andrés Cristi, Laurent Feuilloley and Alexandros Tsginonias-Dimitriadis.


20. November 2020: Bhaskar Ray Chaudhury (MPI Informatik, Saarbrücken)

Titel: TBA

Abstract: TBA

 

Termine vergangner Semester (seit Wintersemester 2019/2020)

 

Termin

Vortragende*r

Titel

21. August 2020

Pan Peng (University of Sheffield)

On Testability of First-Order Properties in Bounded-Degree Graphs

15. Juli 2020

Lin Chen (Texas Tech University)

On block-structured integer programming

10. Juli 2020

Stefan Walzer (TU Ilmenau)

Space Efficient Data Structures using Hashing

26. Juni 2020

Vincent Cohen-Addad (Google Research)

On the Parameterized Complexity of Various Clustering Problems

19. Juni 2020

Pieter Kleer (MPI Informatik, Saarbrücken)

Secretary and Online Matching Problems with Machine Learned Advice

5. Juni 2020

Andrés Cristi (Universidad de Chile)

The two-sided game of Googol and sample-based prophet inequalities

15. Mai 2020

Maximilian Janke (TU München)

Scheduling in the Random-Order Model

8. Mai 2020

Václav Rozhoň (ETH Zürich)

Improved analysis of Lattanzi-Sohler algorithm

24. April 2020

Hendrik Fichtenberger (TU Dortmund)

Size Doesn't Matter: Approximate Decisions on Graphs

24. Januar 2020

Michael Kapralov (EPFL)

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

10. Januar 2020

Piotr Sankowski (Universität Warschau)

Walking Randomly, Massively, and Efficiently

15. November 2019

Heiko Röglin (Universität Bonn)

 Analysis of Ward's Method