New Approximation Algorithms for Densest k-Subgraph
by Aditya Bhaskara, Moses Charikar, Eden Chlamtac,
Uriel Feige and Aravindan Vijayaraghavan.
Oded's comments
I was and am intrigued by the fact that the design of the algorithm
(for the worst-case problem) was actually guided by the analysis of
the planted randomn instance model. This seems related to the fact
that a key aspect of the problem at hand can be related to structures
that are in some sense random (or better than random, where
deviations from random are employed to the benefit of the algorithm).
The original 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+\epsilon})$ approximation
for any $\epsilon>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.
Back to
list of Oded's choices.