[CSDM] [pvsnp-all] CCI meeting, Fri Feb 8

[Moses S. Charikar]

Dear all,

Here is this Friday's program with titles, abstracts and location.

We will have our monthly CCI meeting on Fri, Feb 8 in CS 402.
This month's meeting is devoted to Edge Disjoint Paths.
We will have talks by three experts who will give us an
overview of the amazing progress in recent years on the
this problem and its variants as well as speculate on what
the future might hold. Schedule is as follows

10:15-11:00 PI meeting
11:00-12:15 Edge-Disjoint Paths in Networks, Sanjeev Khanna
12:15- 1:00 lunch
 1:00- 2:15 Hardness of Edge-Disjoint Paths and Congestion Minimization, Matthew Andrews
 2:15- 2:45 break
 2:45- 4:00 Poly-Logarithmic Approximation for Edge-Disjoint-Paths with Congestion 2, Shi Li

--Moses

Title: Edge-Disjoint Paths in Networks
Sanjeev Khanna, University of Pennsylvania

Abstract:
A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a collection of source-destination pairs in a network, and 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 highly restricted settings. A sequence of ideas developed over the past decade has led to great progress on understanding the approximability of EDP. We will survey some of this progress and highlight some outstanding remaining questions.


Title: Hardness of Edge-Disjoint Paths and Congestion Minimization
Matthew Andrews, Bell Labs

Abstract:
We consider the hardness of approximation of the edge-disjoint-paths and congestion minimization problems. It is known that for c < O(log log n / log log log n), it is hard to obtain an O( (log n)^((1-eps)/(c+1) ) approximation to edge-disjoint-paths, even if congestion c is allowed.The main technique used to prove this result is embedding an instance in a high-girth graph. This has the benefit of restricting the set of paths that the solution can use to a small set of “canonical paths”.     
This talk will have 3 parts.
 i) We will begin by showing how the high-girth technique can be used to create edge-disjoint-path instances with large integrality gaps.

ii) We will provide an overview of how these integrality gaps can be converted into hardness-of-approximation results.

iii) We will discuss the barriers to extending the hardness results further. We will focus on congestion minimization since for that problem there is still an exponential gap between the best-known positive and negative results.   The biggest issue with the high-girth technique is that hardness is directly tied to the length of the canonical path and in a true high-girth instance the length of the canonical paths cannot be larger than log n.  We will discuss alternative techniques that relax the high-girth requirement and may allow us to increase the length of the canonical paths, thereby improving the eventual hardness result.


Title :  Poly-Logarithmic Approximation for Edge-Disjoint-Paths with Congestion 2
Shi Li, Princeton University

Abstract : Edge-Disjoint Paths (EDP) problem is one of the central and most extensively studied network routing problems. In the problem, we are given k source-sink pairs in a network and want to connect as many pairs as possible using edge-disjoint paths. In spite of its rich history, there is still a huge gap between the sqrt(log n)-hardness of approximation and the sqrt(n)-approximation ratio for the problem. In this talk, I will give an overview of my joint work with Chuzhoy, which gives a poly-logarithmic approximation for EDP by slightly relaxing the edge-disjointness constraint : we allow each edge in the network to be used twice (i.e, we allow congestion 2). This culminates a long line of research on the EDP with congestion problem.  In the talk, I will highlight some of the techniques used in this line.

_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all