ARC Colloquium: Marco-Dick Yun Kuen Cheung - University of Vienna

Event Details

Dani Denton
denton at cc dot gatech dot edu



Summary Sentence: Klaus 1116 West at 1 pm

Full Summary: No summary paragraph submitted.

Algorithms & Randomness Center (ARC)

Marco-Dick Yun Kuen Cheung  - University of Vienna

Monday, February 29, 20116

Klaus 1116 West - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Graph Minors for Preserving Terminal Distances Approximately

Given a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion.  This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.

We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 / 2.5/ 3  must have \Omega(k^2) / \Omega(k^{5/4}) / \Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any linear (in k) non-terminals will not help improving the lower bound to a constant.

We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with $1+epsilon$ distortion and O(k^2 log^2 k / epsilon^2) non-terminals.


Additional Information

In Campus Calendar

ARC, College of Computing, School of Computer Science

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Feb 15, 2016 - 5:03am
  • Last Updated: Apr 13, 2017 - 5:16pm