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)

Kräftebasiertes Graphenzeichnen mit Hilfe von GPU Ray Tracing Cores

13. November 2020

Tim Oosterwijk (Universität Maastricht)

The Secretary Problem with Independent Sampling

20. November 2020

Bhaskar Ray Chaudhury (MPI Informatik, Saarbrücken)

On the Existence of EFX Allocations

27. November 2020

kein Vortrag

kein Vortrag

4. Dezember 2020

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

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

11. Dezember 2020

kein Vortrag

kein Vortrag

18. Dezember 2020

André Nusser (MPI Informatik, Saarbrücken)

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

8. Januar 2021

kein Vortrag

kein Vortrag

15. Januar 2021

David Scholz (Technische Hochschule Köln)

Generating Optimal 1-Planar Graphs for automated Conjecture-Making

22. Januar 2021

Svenja Griesbach (Unviersität zu Köln)

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

29. Januar 2021

David Weckbecker (Technische Universität Darmstadt)

Unified Greedy Approximability Beyond Submodular Maximization

5. Februar 2021

TBA

TBA

12. Februar 2021

TBA

TBA

 

Abstracts

 

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

Titel: Kräftebasiertes Graphenzeichnen mit Hilfe von GPU Ray Tracing Cores

Abstract:

Im Vortrag stelle ich zunächst meine Person und meine wichtigsten Kooperationen, und danach beispielhaft ein Thema aus meiner wissenschaftlichen Arbeit vor. Ray Tracing wird in den allermeisten Fällen dazu verwendet, Bilder von 3D Szenenbe- schreibungen in die 2D Ebene zu projizieren und anschließend zu zeichnen. Durch den Simulationscharakter sind die beim Ray Tracing entstehenden Bilder physikalisch plausibel und sehr realistisch. Mit diesem Aspekt beschäftigt sich auch ein wesentlicher Teil meiner wissenschaftlichen Arbeit. Im Vortrag stelle ich hingegen ein Verfahren vor, mit dem die jüngst von den GPU Herstellern eingeführte Spezial-Hardware ausgenutzt werden kann, um Nachbarschaftssuche in verstreuten Punktedaten, und damit die Anziehungsphase beim kräftebasierten Graphenzeichnen, zu beschleunigen.


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: On the Existence of EFX Allocations

Abstract:

Fair division of indivisible goods is a fundamental problem in mathematics, computer science and economics. The goal of this problem is to distribute m goods to n agents in a "fair" manner, where every agent has a valuation for each subset of goods.

Depending on the notion of fairness, there are a wide range on problems in this field. In this talk, we focus on a relaxation of a very fundamental and quintessential notion of fairness: Envy-Freeness. A division is said to be envy-free if no agent strictly prefers another agent's bundle to her own. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. The existence of EFX allocations is considered one of the most important problems currently in discrete fair division.

In this talk, we briefly cover two important results on EFX allocations:

1) EFX Allocations with Bounded Charity: We can guarantee the existence of EFX allocations for any number of agents and goods, by not allocating few goods (these goods go to charity). These goods are not very valuable to any agent and the total number of such goods is also less.

2) EFX existence for Three Agents: We also show that EFX allocations exist when there are exactly three agents.


4. Dezember 2020: Sándor Kisfaludi-Bak (MPI Informatik, Saarbrücken)

Titel: Gap-ETH-tight approximation scheme for Euclidean TSP

Abstract:

The Euclidean TSP problem aims to find the shortest round trip of a set of n points in Euclidean space. The celebrated approximation scheme of Arora [JACM'98] can produce a (1+epsilon)-approximate tour in d-dimensional space for any fixed positive epsilon and d in polynomial time. The result (and the independently discovered algorithm of Mitchell) sparked a lot of interest in the problem and in approximation schemes for geometric problems in general.

In this talk, we will see an elegant modification to Arora's scheme called "sparsity-sensitive patching", which fine-tunes the granularity with which the tour is simplified. The resulting algorithm has running time 2^O(epsilon^(1-d)) n log n for any fixed d, which is faster than Arora's scheme, and also faster than the approximation scheme of Rao and Smith. In fact, the epsilon-dependence of our algorithm is optimal under the Gap Exponential Time Hypothesis.

The talk is based on joint work with Jesper Nederlof and Karol Wegrzycki. A preprint is available at https://arxiv.org/abs/2011.03778


18. Dezember 2020: André Nusser (MPI Informatik, Saarbrücken)

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

Abstract:

Computing the similarity between polygonal curves is an important subtask for analyzing animal behavior, classifying handwritten characters, map matching, sports analysis, and many more applications. The Fréchet distance provides a natural and intuitive measure for the similarity of two polygonal curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fréchet distance, in particular for realistic input curves, are highly desirable.

We present a fast implementation for deciding the Fréchet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve over the state-of-the-art implementation. We experimentally evaluate our implementation on a large benchmark consisting of several data sets, observing running-time improvements of more than two orders of magnitude compared to the previous state of the art.

Now, consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified whenever we aim to quantify the similarity of the curves' shapes rather than their positioning in the plane, e.g., to compare the similarity of handwritten characters or detect position-independent motion patterns in GPS trajectories. Using the fast implementation for the Fréchet distance, we now also perform algorithm engineering for the Fréchet distance under translation. Our solution combines fast but inexact tools from continuous optimization with exact but expensive algorithms from computational geometry. We combine these two ingredients to obtain an exact decision algorithm for the Fréchet distance under translation.


15. Januar 2021: David Scholz (Technische Hochschule Köln)

Titel: Generating Optimal 1-Planar Graphs for automated Conjecture-Making

Abstract:

A graph is 1-planar if it can be embedded in the plane such that each edge crosses at most once. If a 1-planar graph with n vertices has 4n-8 edges, it is called optimal 1-planar. It is known that optimal 1-planar graphs can be obtained by generating simple quadrangulations and adding the crossing diagonals in each face. Automated conjecture-making is the process of generating computer-aided new relations between invariants of the object of interest. We implement an algorithm for generating optimal 1-planar graphs using the results of Brinkman et al. and process the algorithm's output to a conjecture-making program by Larson and Van Cleemput.

In this talk, we proceed as follows:

a) We present the set of expansion rules for the generation of the simple quadrangulations implemented in the program 'plantri',
b) We implement an algorithm for generating all optimal 1-planar graphs up to isomorphism,
c) We give a brief introduction to automated conjecture-making and the Fajtlowicz-Dalmatian Heuristic for filtering insignificant conjectures,
d) We process the output of b) to an automated conjecture-making program in order to discover upper bounds for the independence number of optimal 1-planar graphs. 


22. Januar 2021: Svenja Griesbach (Universität zu Köln)

Titel: Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Abstract:

An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.

This talk is based on joint work with Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou.


29. Januar 2021: David Weckbecker (Technische Universität Darmstadt)

Titel: Unified Greedy Approximability Beyond Submodular Maximization

Abstract:

We consider classes of objective functions of cardinality constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of γ-α-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, α-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient - as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of αγ⋅(eα)/(eα−1) on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for α-augmentable functions. In paritcular, as a by-product, we close a gap left in [Math.Prog., 2020] by obtaining a tight lower bound for α-augmentable functions for all α ≥ 1. For weighted rank functions of independence systems, our tight bound becomes αγ, which recovers the known bound of 1/q for independence systems of rank quotient at least q.

This talk is based on joint work with Yann Disser.

 

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