moteur de recherche

Séminaires de Boris Bukh et Otfried Cheong
Séminaires de Boris Bukh et Otfried Cheong
2-juin-2017 14:00
Il y a: 24 days

Salle 4B09R du bâtiment Copernic

14:00 - Boris Bukh

Algebraic methods in extremal combinatorics


Extremal combinatorics is an analytic subject. Its results take the form of inequalities, and its best-known tools are estimates of various kinds. The algebraic tools are less known, but they are extremely powerful in the situations where they apply. These lectures will introduce some of these tools, and their applications. Topics are likely to include restricted set intersections, finite field Kakeya problem, constructions on good Ramsey and Turan graphs, recent solution to the capset problem. The pace and topics will be adjusted in response to the audience.

15:15 - Otfried Cheong


Putting your coin collection on a shelf


Imagine you want to present your collection of n coins on a shelf, taking as little space as possible – how should you arrange the coins?

More precisely, we are given n circular disks of different radii, and we want to place them in the plane so that they touch the x-axis from above, such that no two disks overlap. The goal is to minimize the length of the range from the leftmost point on a disk to the rightmost point on a disk.

On this seemingly innocent problem we will meet a wide range of algorithmic concepts: An efficient algorithm for a special case, an NP-hardness proof, an approximation algorithm with a guaranteed approximation factor, APX-hardness, and a quasi-polynomial time approximation scheme.

Joint work with Helmut Alt, Peyman Afshani, Kevin Buchin, Steven Chaplick, Philipp Kindermann, Christian Knauer, Fabian Stehn.

<- retour: