Sanjeev Arora, paper's coauthor, but also leading expert on approximations to NP-hard problems, has posted a FAQ detailing why he thinks no approximation would

Sanjeev Arora, paper's coauthor, but also leading expert on approximations to NP-hard problems, has posted a FAQ detailing why he thinks no approximation would help, http://www.cs.princeton.edu/~rongge/derivativeFAQ.html http://www.cs.princeton.edu/~rongge/derivativeFAQ.html And also his response to RJ Lipton who believes approximation ought to work (but then again Lipton believes P=NP, so for him nothing is impossible): http://rjlipton.wordpress.com/2009/10/22/helping-wall-street-cheat-with-theory/#comment-1756 http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... These are mostly practical reservations, carefully stated as to convince of intractability in the real-world case (which they do) but not prove in theory. Excerpt: current pricing and rating algorithms use monte carlo methods and would not solve densest subgraphs even for moderate parameters. So at the very least those should be changed. Turns out problem they reduced their model to is open in terms of finding good approximation to it. Excerpt from the FAQ: The paper relies upon a stronger form of "P not equals NP", namely, that the planted dense subgraph problem does not have an efficient algorithm. (In fact it is conjectured that there is no algorithm to even compute any approximate solutions to this problem).