Building wireless networks and routing on them

Abstract:

In this talk I will talk about a network problem that showcases the kind of research problems I work on. A routing scheme $\Rr$ in a network $G=(V,E)$ is an algorithm that allows to send messages from one node to another in the network. 

Given the location of the nodes, we first consider a preprocessing phase in which we construct the network (if possible, we also assing\emph{routing table} with additional information to each node). After this preprocessing, we give a local routing (i.e., we can only use the information from the label of the target and the routing table of the node that we are currently at). 

We present a network construction algorithm paired with a routing scheme in the presence of obstacles: if we are not allowed a routing table, each node stores a constant amount of information and the messages are guaranteed to arrive. If we are allowed a routing table of size of size $\Oe(\eps^{-1}\log n)$ per node, the routing scheme provides a stretch of $1+\eps$  for any $\eps > 0$. is $\Oe(n^2+\eps^{-1}n)$. This improves the best known strategies for general graphs by Roditty and Tov (Distributed Computing 2016).

Biography:

Matias Korman is an assistant professor at Tohoku University (Japan). His research focuses in the design of algorithms with strong geometric components. Specifically, he is interested in problems related to shortest paths, memory constrained algorithms, and/or wireless networks.