Aravindan Vijayaraghavan
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph.
Tue, 01/19/2010 - 16:01 — SomNambulAuthors: Uriel Feige, Aditya Bhaskara, Aravindan Vijayaraghavan, Moses Charikar, Eden Chlamtac
Subjects: Data Structures and Algorithms
AbstractIn the Densest k-Subgraph problem, given a graph G and a parameter k, one
needs to find a subgraph of G induced on k vertices that contains the largest
number of edges. There is a significant gap between the best known upper and
lower bounds for this problem. It is NP-hard, and does not have a PTAS unless
NP has subexponential time algorithms. On the other hand, the current best
known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of
n^(1/3-epsilon) for some specific epsilon > 0 (estimated at around 1/60).Computing the Matrix p-norm.
Mon, 01/18/2010 - 16:01 — SomNambulAuthors: Aditya Bhaskara, Aravindan Vijayaraghavan
Subjects: Data Structures and Algorithms
AbstractA matrix is said to be positive if all its entries are >0. We consider n x n
positive matrices where the ratio of the largest to smallest entry is at most
N, for some parameter N. We show that for any p>1, the p-norm of the matrix,
which is defined to be |A|_p = Max_x ||Ax||_p, where ||x||_p=1 can be computed
to a factor of (1+$\delta$) in time polynomial in $\log(1/\delta)$, N and the
dimension of the matrix n.
User login
