Reproduce “Constant-Factor Local Approximation for Bipartite Densest Subgraph” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Michael Kapralov, Jakub Łącki, Silvio Lattanzi, Guy Weissenberg
The authors present a local algorithm for finding a dense pair in a bipartite graph from a vertex in a cohesive target. It uses peeling. For targets with at most k vertices per side, it returns density at least √3/(16√e)·ε/(1+ε) times target density, with Oε(k^(2+ε)) output vertices and Oε(k^(4+ε)) neighbor queries; its output need not overlap the target.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.