PhD from U of Chicago, USA. Currently a postdoc at MPI.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

In networking, we often need an algorithm that routes packets over the internet, ensuring that certain "quality" criteria are met. One such
goal is to route as many packets as possible without overloading any
single link in the network. This particular problem corresponds to the
well-known EDP (Edge-Disjoint Paths) problem which has been extensively
studied over the past decade. Ideally for any routing problem, we do
not want to overload any link in the network, but sometimes such
constraint can be relaxed to allow a constant congestion, i.e. the
number of packets on each link is at most a constant times its
capacity. This would guarantee that the network does not slow down by
too much.

Many quality criteria, however, cannot be provided by the
EDP algorithm, for instance, ``fairness'' of routing algorithms in
the following sense. Suppose there are 100 demands, each asking for
10MB of data to be sent. The EDP algorithm may choose to route 70
demands (10MB for each), while leaving the other 30 unserved. Of
course, this would not be fair to those unserved demands, although the
network is utilized effectively. Now a natural question arises: Is it
possible to simultaneously route a large fraction of data for EVERY
demand pair?

We address this question by initiating the study of Integral Concurrent
Flow (ICF) problem to capture the notion of ``fair routing''. We devise
a poly-logarithmic factor approximation algorithm with constant
congestion, as well as proving some lower bounds and connections to
other central problems in approximation algorithms.

(joint work with J. Chuzhoy, A. Ene, and S. Li, STOC 2012 )

Parinya Chalermsook

--email hidden

passcode not visible

logged in users only