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
> FEB 12: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
FEB 12: Theory CS Seminar
Event date: Friday, February 12, 2010, at 11:10 AM
Location: Galbraith Bldg, Rm. 244
Speaker: Eden Chlamtac
Weizmann Institute of Science
Title: New Approximation Algorithms for Densest k-Subgraph
Abstract: We consider the Densest k-Subgraph (DkS) problem: Given a graph G and a parameter k, find a subgraph of G on k vertices with the maximum number of edges. This is a well known optimization problem, which is a natural optimization version of the decision problem k-CLIQUE.
The previous best known approximation ratio by Feige, Kortsarz and Peleg in 2001 was O(n^{1/3-epsilon}) for epsilon estimated at around 1/60. We improve on this result, giving an O(n^{1/4+delta}) approximation for any delta>0.
In essence, our algorithm relies on the following principle: In a random graph with average degree n^alpha, a planted k-subgraph can be detected if it has average degree (strictly) greater than k^alpha. We show that this principle largely carries over to provide results in the same spirit for worst-case (non-random) instances.
Joint work with Aditya Bhaskara, Moses Charikar, Uriel Feige and Aravindan Vijayaraghavan.