Back to search

Georgia Institute of Technology

Dual algorithms for the densest subgraph problem

Abstract

dc:description.abstract

Dense subgraph discovery is an important primitive for many real-world graph mining applications. The dissertation tackles the densest subgraph problem via its dual linear programming formulation. Particularly, our contributions in this thesis are the following: (i) We give a faster width-dependent algorithm to solve mixed packing and covering LPs, a class of problems that is fundamental to combinatorial optimization in computer science and operations research (the dual of the densest subgraph problem is an instance of this class of linear programs) . Our work utilizes the framework of area convexity introduced by Sherman [STOC `17] to obtain accelerated rates of convergence. (ii) We devise an iterative algorithm for the densest subgraph problem which naturally generalizes Charikar's greedy algorithm. Our algorithm draws insights from the iterative approaches from convex optimization, and also exploits the dual interpretation of the densest subgraph problem. We have empirical evidence that our algorithm is much more robust against the structural heterogeneities in real-world datasets, and converges to the optimal subgraph density even when the simple greedy algorithm fails. (iii) Lastly, we design the first fully-dynamic algorithm which maintains a (1-ε) approximate densest subgraph in worst-case \text{poly}(\log n, ε-1) time per update. Our result improves upon the previous best approximation factor of (1/4 - ε) for fully dynamic densest subgraph.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sawlani, Saurabh Sunil Sunil
Advisor dc:contributor.advisor
  • Peng, Richard
Committee members dc:contributor.committeemember
  • Randall, Dana
  • Vigoda, Eric
  • Yu, Xingxing
  • Tsourakakis, Charalampos E.

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/63582

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sawlani, Saurabh Sunil Sunil. Dual algorithms for the densest subgraph problem. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/63582