Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Research Seminar (Winter Term 2019)

<previous seminar | next seminar>

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich or to Ralf Rothenberger.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

Date Room Speaker Title
22.10. 15:30 G1.E 15/16 Martin Schirneck

A unique column combination (UCC) is a small fingerprint of a relational database. Enumerating all inclusion-wise minimal UCCs is therefore a reoccurring task in data profiling. In this talk we explore the close connection between UCCs and the hitting set problem. We show how this connection leads to new enumeration algorithms. In particular, we present a technique that combines a sampling strategy for databases with an input-guided search heuristic to find hitting sets. A preliminary experimental evaluation indicates that our approach is not only competitive with the current state-of-the-art UCC algorithm, but can process databases that were previously out of reach for data profiling.

The talk presents ongoing research with Johann Birnick, Thomas Bläsius, Tobias Friedrich, Julius Lischeid, Felix Naumann, Kitty Meeks, and Thorsten Papenbrock.

30.10. 15:00 A-2.2 Fabian Sommer

Hyperbolic random graphs have become a popular random graph model over the last decade, as they resemble many real-world graphs. In particular, they have a heterogeneous degree distribution, high clustering and a small-world property. Another property of graphs that distinguishes technical and biological from social networks is degree assortativity – a measure that describes the correlation between degrees of adjacent nodes. Most technical and biological graphs are found to have a significant negative assortativity, while the assortativity of social networks is usually positive. However, hyperbolic random graphs offer no way to control the degree assortativity.

We explore and compare multiple ways to extend hyperbolic random graphs or the similar geometric inhomogeneous random graphs so that the expected assortativity can be controlled while maintaining the properties that made hyperbolic random graphs attractive in the first place. In particular, we describe a model with controllable assortativity that has high clustering, small-world and a heterogeneous degree distribution. We also describe how such graphs can be generated efficiently.

08.11. 13:00 A-1.1 Master Project Summer 2019

Asymmetric instances for the travelling salesman problem are practically relevant, but still there is a big gap in approximation guarantees between symmetric and asymmetric instances (assuming triangle inequality in either case). We explore this apparent difference between symmetry and asymmetry by generalizing the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the number of asymmetric edges in a given minimum spanning arborescence. Both algorithms are also stated in the form of additive lossy kernelizations, which allows to combine them with known polynomial time approximations for ATSP. Further, we combine them with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime.

26.11. 13:30 H-E.51 Maximilian Katzmann

TBA

03.12. 13:30 H-E.51 Ziena Elijazyfer

TBA