Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - October 14
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - October 14
Event date: Friday, October 14, 2011, at 2:10 PM
Location: PT266
SPEAKER: Eden Chlamtac
Tel Aviv University
TITLE: Sparse Spanners via Dense Subgraphs
ABSTRACT:
A spanner (of a graph) with stretch s (an s-spanner) is a subset of edges of the graph for which the shortest path metric is preserved up to a factor s. Spanners have a number of applications ranging from parallel and distributed computing to property testing. We focus on the Lowest-Degree 2-Spanner (LD2S) problem, where we wish to find a 2-spanner of a graph with unit edge lengths, while minimizing the maximum degree in the spanner. This problem was previously studied by Kortsarz and Peleg [SODA'94; Siam J. Comp.'98], who gave a\tilde{O}(Delta^{1/4}) approximation, where Delta is the maximum degree in the original graph. We improve on this by giving a \tilde{O}(Delta^c) approximation, where c = 3-2\sqrt{2} = 0.17...
Our algorithm exploits a surprising new connection to the Smallest m-Edge Subgraph (SmES) problem, for which we give a \tilde{O}(n^c) approximation, by using an LP-hierarchy based framework which was developed in recent work on Densest k-Subgraph.
In order to use our SmES algorithm in the context of spanners, it is crucial that in our LP rounding both vertices and edges are chosen with probabilities proportional to their LP values. This novel and relatively strong condition is achieved despite the fact that the rounding relies on information from higher-moment variables in the LP hierarchy, rather than directly using LP variables corresponding to vertices and edges.
This is based on joint work with Michael Dinitz and Robert Krauthgamer.