zum Inhalt springen

Kolloquium über Informatik

Termine Sommersemester 2021

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




16. April 2021

Katarzyna Bozek (Center for Molecular Medicine Cologne, University of Cologne)

Data science of bioimages

23. April 2021

kein Vortrag

kein Vortrag

30. April 2021

kein Vortrag

kein Vortrag

7. Mai 2021

kein Vortrag

kein Vortrag

14. Mai 2021

kein Vortrag

kein Vortrag

21. Mai 2021

kein Vortrag

kein Vortrag

4. Juni 2021

kein Vortrag

kein Vortrag

11. Juni 2021

kein Vortrag

kein Vortrag

18. Juni 2021

Antonios Antoniadis (University of Twente)

Minimizing Energy Consumption on Multiple Machines with Sleep States

25. Juni 2021

kein Vortrag

kein Vortrag

2. Juli 2021

kein Vortrag

kein Vortrag

9. Juli 2021

kein Vortrag

kein Vortrag

16. Juli 2021

kein Vortrag

kein Vortrag

23. Juli 2021 (15:00 Uhr!)

Andrés Cristi (Universidad de Chile)

Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality




16. April 2021: Katarzyna Bozek (Universität zu Köln)

Titel: Data science of bioimages


In this talk I will introduce research done in my group “Data science of bioimages”. I will use my recent work on dense object tracking as an example to illustrate challenges of bioimage analysis as well as opportunities it presents for method advancement in computer vision. Across the various projects performed in my group we encounter challenges that often cannot be resolved with existing computer vision methods. Our solutions therefore require method development drawing knowledge not only from computer vision and machine learning but also from process parallelization or algorithm optimization. While computational biology has grown into an established field, the recent progress in deep learning gave rise to a new area of computer vision in biology with few yet existing standard methods.

18. Juni 2021: Antonios Antoniadis (University of Twente)

Titel: Minimizing Energy Consumption on Multiple Machines with Sleep States


The talk is about the problem of minimizing energy consumption on multiple machines with sleep states: We are given n jobs, each with a release date, a deadline and a processing time, and wish to schedule them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time.

The core of the talk revolves around giving a 2-approximation algorithm for the single machine case. The algorithm is based on the solution of a linear programming relaxation, which can be decomposed into a convex combination of integer solutions. However none of them may be feasible since the linear programming relaxation has a strictly positive integrality gap. We discuss how such an integer solution can nevertheless be turned into a feasible solution without increasing the cost by too much. We outline how these ideas can be extended in order to obtain the first known constant approximation for the multiprocessor setting (with an approximation factor of 3), before concluding the talk by discussing how the latter algorithm can be adapted to obtain an approximation ratio of 2, and how one can circumvent the linear-programming formulation in order to obtain a combinatorial O(1)-competitive algorithm from the problem.

The talk is based on joint work with Naveen Garg, Gunjan Kumar and Nikhil Kumar (SODA '20).

23. Juli 2021: Andrés Cristi (Universidad de Chile)

Titel: Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality


We take a unifying approach to single selection optimal stopping problems with random arrival order and independent sampling of items. In the problem we consider, a decision maker (DM) initially gets to sample each of N items independently with probability p, and can observe the relative rankings of these sampled items. Then, the DM faces the remaining items in an online fashion, observing the relative rankings of all revealed items. While scanning the sequence the DM makes irrevocable stop/continue decisions and her reward for stopping the sequence facing the item with rank i is Yi. The goal of the DM is to maximize her reward. We start by studying the case in which the values Yi are known to the DM, and then move to the case in which these values are adversarial.

In this talk I will first present a linear program that captures the performance of an algorithm in the case where the values are known, and take its continuous limit by infinitely extending the sequence. I will show how we can recover classic results in the area such as those for the secretary problem, and the minimum ranking problem.

Then, I will show how we can reformulate the linear program with an additional stochastic dominance constraint to capture the case where the values are adversarial. By using the same machinery we are able to pin down the optimal algorithm for this problem, obtaining the optimal competitive ratios for all values of p. Notably, we prove that as p approaches 1, our guarantee approaches 0.745, matching that of the i.i.d. prophet inequality.


Termine vergangener Semester (seit Wintersemester 2019/2020)





12. Februar 2021

Felix Hommelsheim (Technische Universität Dortmund)

Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity

29. Januar 2021

David Weckbecker (Technische Universität Darmstadt)

Unified Greedy Approximability Beyond Submodular Maximization

22. Januar 2021

Svenja Griesbach (Unviersität zu Köln)

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

15. Januar 2021

David Scholz (Technische Hochschule Köln)

Generating Optimal 1-Planar Graphs for automated Conjecture-Making

18. Dezember 2020

André Nusser (MPI Informatik, Saarbrücken)

Algorithm Engineering of the Fréchet Distance & the Fréchet Distance Under Translation

4. Dezember 2020

Sándor Kisfaludi-Bak (MPI Informatik, Saarbrücken)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

20. November 2020

Bhaskar Ray Chaudhury (MPI Informatik, Saarbrücken)

On the Existence of EFX Allocations

13. November 2020

Tim Oosterwijk (Universität Maastricht)

The Secretary Problem with Independent Sampling

6. November 2020

Stefan Zellmann (Universität zu Köln)

Kräftebasiertes Graphenzeichnen mit Hilfe von GPU Ray Tracing Cores

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