## Infomation

Category | 2017 Math Colloquium | ||
---|---|---|---|

날짜 | 2017-04-07 | 시간 | 15:50:00 ~ 18:00:00 |

장소 | Math Sci Bldg 404 | ||

Speaker | Otfried Cheong | Host | Kang Tae Kim |

소속 | KAIST | ||

TOPIC | I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf |

## Abstract

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.

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.