Kolloquium über Informatik
Termine Wintersemester 2020/2021
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
4. Dezember 2020
Sándor Kisfaludi-Bak (MPI Informatik, Saarbrücken)
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
11. Dezember 2020
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
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
12. Februar 2021
6. November 2020: Stefan Zellmann (Universität zu Köln)
Titel: Kräftebasiertes Graphenzeichnen mit Hilfe von GPU Ray Tracing Cores
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
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
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
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
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
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
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
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)
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