Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Dieter Spreen, Bi-Topological Spaces and the Continuity Problem

Sunday, April 9th, 2017
Bi-Topological Spaces and the Continuity Problem
Dieter Spreen
Department of Mathematics, Universität Siegen, Siegen, Germany
2017/4/17 Mon 4PM-5PM
The continuity problem is the question when effective (or Markov computable) maps between effectively given topological spaces are effectively continuous. It will be shown that this is always the case if the the range of the map is effectively bi-regular. As will be shown, such spaces appear quite naturally in the context of the problem.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Otfried Cheong, Putting your coin collection on a shelf

Saturday, March 18th, 2017
Putting your coin collection on a shelf
Otfried Cheong
School of Computing, KAIST
2017/04/03 Monday 4PM-5PM
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.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

[SoC Colloquium] Helmut Alt, Packing Problems: Algorithms and Complexity

Tuesday, March 7th, 2017
Packing Problems: Algorithms and Complexity
Helmut Alt
Department of Computer Science, Freie Universität Berlin
2017/3/13 Mon 4PM-6PM
Packing problems are concerned with positioning geometric objects so that they do not overlap and require an amount of space as small as possible. They have been investigated within mathematics for centuries starting with the famous Kepler conjecture. There are many surprising properties and open problems in connection with packing. The lecture will give a short survey about these “classical” issues but then concentrate on algorithms for packing. Since already the most simple variants are NP-hard, it makes sense to look for efficient approximation algorithms. We will present constant factor approximations for packing rectangles and convex polygons into containers which are minimum area rectangles or convex sets. Algorithms for analogous problems concerning three-dimensional objects will be presented, as well.
This is joint research with Mark de Berg, Christian Knauer, Léonard von Niederhäusern, and Nadja Scharf.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Bernard Lidický, 3-coloring triangle-free planar graphs

Wednesday, March 1st, 2017
3-coloring triangle-free planar graphs
Bernard Lidický
Department of Mathematics, Iowa State University, Ames, IA, USA
2017/3/7 Tue 4PM
A well known theorem of Grötzsch states that every planar graph is 3-colorable. We will show a simple proof based on a recent result of Kostochka and Yancey on the number of edges in 4-critical graphs. Then we show a strengthening of the Grötzsch’s theorem in several different directions. Based on joint works with Ilkyoo Choi, Jan Ekstein, Zdeněk Dvořák, Přemek Holub, Alexandr Kostochka, and Matthew Yancey.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Suil O (오수일), The second largest eigenvalue and vertex-connectivity in regular graphs

Monday, January 23rd, 2017
The second largest eigenvalue and vertex-connectivity in regular graphs
Suil O (오수일)
Department of Applied Mathematics & Statistics, SUNY Korea, Incheon
2017/2/3 Fri 4PM-5PM
In this talk, for a fixed positive integer d at least 3, we study upper
bounds for the second largest eigenvalue in (an n-vertex) d-regular graph to
guarantee a certain vertex-connectivity.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »