Department of Mathematics, POSTECH


Category 2017 Math Colloquium
날짜 2017-04-07 시간 15:50:00 ~ 18:00:00
장소 Math Sci Bldg 404
Speaker Otfried Cheong Host Kang Tae Kim
TOPIC I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf


I Title: Counting and generating with the Catalan Numbers - a historical note
I Abstract: In this talk we will see how the Catalan numbers and their properties
were discovered by Euler, Segner, and Lame, use the
Multiply-Decorate-Biject technique to prove the Catalan recurrence,
and see how this constructive proof directly leads to an efficient
method for generating structures uniformly at random.

II Title: Putting your coin collection on a shelf
II Abstract: 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.