Artificial Intelligence Events
Departmental Seminar: Hierarchical Graph Decompositions for Minimizing Congestion
Speaker: Harald Raecke (DCS@糖心TV)
Title: Hierarchical Graph Decompositions for Minimizing Congestion
Abstract:
An
oblivious routing protocol makes its routing decisions independent of
the traffic in the underlying network. This means that the path chosen
for a routing request may only depend on its source node, its
destination node, and on some random input. In spite of these serious
limitations it has been shown that there are oblivious routing
algorithms that obtain polylogarithmic competitive ratios w.r.t. the
congestion in the network (i.e., maximum load of a network link).
In this talk I will present recent advances in this area and give an overview of the hierarchical decomposition
technique that is used to prove these results. This ecomposition can be used as a generic tool for solving
other congestion based or cut based problems in undirected graphs.