Cutting corners cheaply, or how to remove Steiner points

Speaker: Huy Le Nguyen , Princeton

Date: Wednesday, October 09, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ronitt Rubinfeld

Contact: Ilya Razenshteyn, ilyaraz@csail.mit.edu

Relevant URL: http://www.ilyaraz.org/acseminar/

Speaker URL: None

Speaker Photo:
None

Reminders to: compalgsem@lists.csail.mit.edu, theory-seminars@lists.csail.mit.edu

Reminder Subject: TALK: Cutting corners cheaply, or how to remove Steiner points

Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, we prove that for every edge-weighted graph $G = (V,E,w)$ and a subset of terminals $T \subseteq V$, there is a graph $G'=(T,E',w')$ that is isomorphic to a minor of $G$, such that for every two terminals $u,v\in T$, the shortest-path distances between them in $G$ and in $G'$ satisfy $d_{G,w}(u,v) \le d_{G',w'}(u,v) \le O(\log^6|T|) \cdot d_{G,w}(u,v)$. Our existence proof actually gives a randomized polynomial-time algorithm.

Our proof features a new variant of metric decomposition. It is well-known that every finite metric space $(X,d)$ admits a $\beta$-separating decomposition for $\beta=O(\log |X|)$, which roughly means for every desired diameter bound $\Delta>0$ there is a randomized partitioning of $X$, which satisfies the following separation requirement: for every $x,y \in X$, the probability they lie in different clusters of the partition is at most $\beta\,d(x,y)/\Delta$. We introduce an additional requirement, which is the following tail bound: for every shortest-path $P$ of length $d(P) \leq \Delta/\beta$, the number of clusters of the partition that meet the path $P$, denoted $Z_P$, satisfies $\Pr[Z_P > t] \le 2e^{-\Omega(t)}$ for all $t>0$.

Joint work with Lior Kamma and Robert Krauthgamer.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Ilya Razenshteyn at Monday, September 23, 2013 at 12:12 PM.