Large 00004

Edge-Disjoint Paths in Networks

Sanjeev Khanna

Recorded 13 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a network and a collection of source-destination pairs in the network. The goal is to maximize the number of pairs that can be connected by edge-disjoint paths. Even special cases of EDP correspond to non-trivial optimization problems, and the problem becomes NP-hard in very restricted settings. We will survey some recent progress on understanding the approximability threshold of EDP.

Watched 1076 times.