Seminars

View all Seminars  |  Download ICal for this event

Geometry, networks, and algorithms

Series: Institute lecture

Speaker: Prof. Mark de Berg, Professor, TU Eindhoven

Date/Time: Jul 06 14:00:00

Location: Faculty Hall, Indian Institute of Science

Abstract:
Optimization problems on networks are among the most widely studied problems studied in algorithms research. In many applications, the networks are geometric: each node in the network has a location, and the edges in the network are either physical connections (for example, in a road network) or they are induced by the distances between the nodes (for example, in a wireless sensor network). In this talk, I will discuss recent techniques on various fundamental problems on geometric networks, including INDEPENDENT SET, the TRAVELING SALESMAN PROBLEM, and SINGLE-SOURCE SHORTEST PATHS. These techniques lead to theoretically optimal, or near-optimal, solutions that are significantly faster than what can be obtained for arbitrary non-geometric networks.

Speaker Bio:
Mark de Berg received an MSc in computer science from Utrecht University (the Netherlands) in 1988, and a PhD from the same university in 1992. Currently, he is a full professor at TU Eindhoven. He is (co-)author of two books on computational geometry, one of which has become the standard textbook in the field, and he has published over 300 papers in journals and peer-reviewed conferences. Mark currently serves on the editorial board of three international journals (SICOMP, Algorithmica, and JoCG) and he was on the program committee of many international conferences. He is a former chair  of the Steering Committee of the European Symposium on Algorithms, he served several times as an elected member of the Computational-Geometry Steering Committee.

Host Faculty: Prof. Rahul Saladi