IPA In Person Algorithmics Course Day March 7th 2022

An IPA course day will take place Monday March 7th, 2022, starting at 10:00.

The course day will consist of two parts, to be presented by Erik Jan van Leeuwen (UU) and Mark de Berg (TU/e) respectively.

This course day will go ahead and be in person.

Venue

Due to unforeseen circumstances, the venue has changed to the Senaatszaal, TU/e campus (building Auditorium / 1, map area B4). The venue is within 10 minutes walking from Eindhoven Centraal train station. Paid parking is available on campus, a.o. next to the Auditorium building.

Room 134 in Marinus Ruppert building, Utrecht University Science Park. The venue is within 5-7 minutes walking from

• sneltram (line 22) stop Heidelberglaan, giving a direct connection to Utrecht Centraal train station in 12 minutes;
• car parkings P9 Budapestlaan and P6 Padualaan.

Content

Morning session (10:00–12:30) — Erik Jan van Leeuwen, Parameterized Planar Problems: Bidimensionality and Beyond.
A cornerstone of the algorithmic toolkit for planar graphs is the bidimensionality framework. It enables efficient parameterized and approximation algorithms for a multitude of optimization problems. However, many connectivity and cut problems, such as Steiner Tree and Multiway Cut, are not covered by this framework. As such, many intriguing questions for parameterized problems on planar graphs had remained open. Recent algorithms have been able to bridge this gap and yield results that are likely best possible in the sense of worst-case running time. The lectures will survey this evolution of the field in the past years and highlight important techniques and ideas, such as treewidth algorithms and lower bounds through the Exponential Time Hypothesis.

Lunch (12:30–13:45)

Afternoon session (13:45–16:15) — Mark de Berg, Randomized Incremental Geometric Algorithms.
Randomized Incremental Construction (RIC) is a beautiful and powerful technique, which gives simple and efficient solutions to a variety of algorithmic problems. In this lecture I will present this technique and discuss several geometric applications of it, including the computation of convex hulls and Delaunay triangulations. I will also discuss a variant called lazy randomized incremental construction, which can sometimes be used in cases where standard RIC cannot be applied.

IPA’s Advanced Courses

IPA organises Advanced Courses on each of its major research fields: Algorithmics and Complexity, Formal Methods and Software Technology. Each of these Advanced Courses intends to give an overview of (part of) the research of IPA in this specific field.

The Advanced Courses focus on subject areas where successful research is being conducted by groups in IPA, with some prominent (inter)national speakers as well. Course components consist of lectures mixed with active training (exercises, assignments, etc.).

Outside pandemic times, these Advanced Courses are scheduled as five consecutive course days on site, typically at TU/e. For now, we instead schedule a series of standalone course days for each of the three research fields. We will determine whether these are held online or in person (hopefully!) based on Covid restrictions at the time.

Required for Credit

As part of the IPA educational programme, IPA PhD candidates are required to follow the three advanced courses but are exempted for the advanced course that covers the field of specialisation of the candidate (but welcome to follow it). Following the Advanced Course for a field and obtaining credit for it (2 ECTS) normally requires attending at least 4 course days from that field’s course week; in pandemic times, it requires attending 4 course days from the course day series for the field.

Registration and preparation

Please register ASAP (we just ask for your e-mail, first and last name, affiliation, and background (IPA / non-IPA, PhD student / staff member; and any dietary requirements for lunch).

Registration closes Monday February 28th 10:00 AM.

Schedule

The overall schedule of the course days is as follows: course days will start at 10.00 and last until approximately 16.00 hours. There will be one or two short breaks in the morning and afternoon at the discretion of the lecturer, and a longer lunch break at, roughly, 12.15-13.30.