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

[Moses S. Charikar]

The Princeton area has a winter storm warning from 3pm onwards.
We will have our CCI meeting today as planned. Due to the 
imminent storm, we will compress the schedule somewhat to 
end earlier. In particular, we'll start the second talk
early and cut the break before the last talk, so we should
be able to end about 45 min earlier than the original schedule.

--Moses

----- Original Message -----
> 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