I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf
|분야Field||2017 Math Colloquium|
|날짜Date||2017-04-07||시간Time||15:50 ~ 18:00|
|장소Place||Math Sci Bldg 404||초청자Host||Kang Tae Kim|
|TOPIC||I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf|
|소개 및 안내사항Content||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