Research map / Learning theory and algorithms / Sample complexity
Faster and Scalable Algorithms for Densest Subgraph and Decomposition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace static peeling with fractional peeling (ablation) | Greedy++, FISTA, Frank-Wolfe · real-world graphs | iterations to reach max density | Helped |
| apply fractional peeling to MWU (ablation) | MWU · real-world graphs | iterations to reach max density | No clear effect |
| parallelize FISTA instead of sequential Greedy++ | FISTA-Parallel · real-world graphs | time per iteration: roughly 5 fold | Helped |
Closest papers by meaning
- Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems (ICML 2024 · similarity 0.90)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.90)
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.89)
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.88)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.88)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.