Institut für Theoretische Informatik

Bester Masterabschluss 2016

14.12.2016

Wir gratulieren ganz herzlich Katharina Dannenberg zum besten Masterabschluss der Universität zu Lübeck, der von der Firma Capgemini mit einem Preis in Höhe von 1.000 Euro dotiert wurde.

Promotion von M.Sc. Oliver Witt

06.12.2016

Wir gratulieren ganz herzlich zur erfolgreichen Promotion!

Vortrag von Kim-Manuel Klein, CAU Kiel: About the Structure of the Integer Cone and its Application to Bin Packing

29.11.2016, 16 Uhr c.t., Seminarraum ITCS 2021, Gebäude 64, 2. OG

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoss about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time |V|^{2^{O(d)}}⋅enc(I)^{O(1)}, where V is the set of vertices of the integer knapsack polytope and enc(I) is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope |V|. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.

3rd Creative Mathematical Sciences Communication Conference (CMSC)

4 - 7 October 2016

This is the third event in a conference series that explores new ways of helping students to achieve 21st Century competencies in mathematics and computer science. The previous conferences, held in Darwin, Australia, in 2013 and in Chennai, India, in 2014 (Videos from 2014) saw a unique interaction between computer science / mathematics researchers and educators and artists (theatre, dance, graphic arts). 3rd CMSC 2016

Best Student Paper für Sebastian Berndt

im Juni 2016

Anlässlich der Tagung 4th ACM Workshop on Information Hiding and Multimedia Security im Juni 2016 in Vigo/Spanien, wurde die Arbeit von Sebastian Berndt und Maciej Liskiewicz "Provable Secure Universal Steganography of Optimal Rate" mit dem Best Student Paper Award ausgezeichnet. (Foto v.l.n.r.: Nuria González Prelcic, Patrick Bas, Sebastian Berndt, Fernando Pérez-González)

Forschungsprojekt bewilligt

im Mai 2016

Die Deutsche Forschungsgemeinschaft (DFG) bewilligt dem Institut für Theoretische Informatik ein neues Forschungsprojekt zum Thema "Kausalität: algorithmischer Ansatz und komplexitätstheoretische Perspektive". Weitere Informationen...

Vortrag von Thorsten Ehlers, CAU Kiel: Sorting Networks & SAT

03.05.2016, 16 Uhr c.t., Seminarraum ITCS 2021, Gebäude 64, 2. OG

In this talk I will present some recent results on sorting networks. Sorting networks are sorting algorithms which perform a sequence of comparisons on the input which only depends on the input size. This makes them relevant for hardware implementations. I will show how SAT encodings can be used to determine lower and upper bounds on some properties of sorting networks, and how improved encoding techniques led to new bounds. Finally, I will discuss an application of sorting networks for SAT encodings, so-called cardinality networks.

Zum Überblick Mitarbeiter