Speaker: Mayank Goswami, Queens College (CUNY)
Title: Load Balanced Routing using area-preserving maps and medial axis
Date: November 22, 2016
Place: 1314 Warren Weaver Hall
Time: 6-7pm
Abstract:
Load balanced routing in a network, i.e., minimizing the maximum
traffic load any node carries, is a well known NP-hard problem.
Finding practical algorithms remains a long-standing
challenge. However, one hopes that if the nodes are placed in a
geometric domain, the problem becomes tractable. In this talk we will
summarize two main results:
1) how to use area-preserving maps to achieve load-balanced routing in
simply connected domains, and
2) how to use the medial axis to achieve load balanced routing in
general multiply connected domains. The final goal is to achieve an
O(1) approximation for distributed load balanced routing in general
domains. We will show how to achieve this under the assumption of
uniform distribution of a set of nodes in a geometric domain.