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 ~ 2017-04-07	시간Time	15:50 ~ 18:00
장소Place	Math Sci Bldg 404	초청자Host	Kang Tae Kim
연사Speaker	Otfried Cheong	소속Affiliation	KAIST
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 approximation scheme.

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

성명Field	I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf
날짜Date	2017-04-07 ~ 2017-04-07	시간Time	15:50 ~ 18:00
소속Affiliation	KAIST	초청자Host	Kang Tae Kim
소개 및 안내사항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 approximation scheme.

성명Field	I: Counting and generating with the Catalan Numbers - a historical note, II:Putting your coin collection on a shelf
날짜Date	2017-04-07 ~ 2017-04-07	시간Time	15:50 ~ 18:00
호실Host		인원수Affiliation	Otfried Cheong
사용목적Affiliation	Kang Tae Kim	신청방식Host	KAIST
소개 및 안내사항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 approximation scheme.