Events
This week
×
Modal title
Modal content
Monday, 17 July | |||
---|---|---|---|
— no events scheduled — |
Tuesday, 18 July | |||
---|---|---|---|
Time | Speaker | Title | Location |
13:15 - 14:15 |
Prof. Dr. Chandra Chekuricall_made University of Illinois at Urbana-Champaign |
Abstract
The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected
graph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set
of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice
and have several applications in data mining and network analysis. We study fast algorithms and
structural aspects of DSG via the lens of supermodularity. For this we consider the densest supermodular
subset problem (DSS): given a non-negative supermodular function f over a ground set V, maximize f(S)/|S|.
Greedy peeling algorithms have been very popular for DSG and several variants due to their efficiency,
empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for
DSS and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.
developed an iterative peeling algorithm for DSG which appears to work very well in practice, and made a
conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove
that a natural generalization of their algorithm converges for DSS. In subsequent
work we also showed that the algorithm converges to the densest supermodular set decomposition.
The proofs are based on connections between the LP relaxation for DSG suggested by Charikar,
Lovász extension of a supermodular function, Fujishige's result on lexicographically optimal base
in a (contra) polymatroid, and continuous optimization algorithms such Frank-Wolfe method and Multiplicative
Weight Updates.
Based on joint work in papers with Harb El Farouk, Kent Quanrud and Manuel Torres.
DACO SeminarDensest Subgraph: Supermodularity and Iterative Peelingread_more |
HG G 19.2 |
Wednesday, 19 July | |||
---|---|---|---|
— no events scheduled — |
Thursday, 20 July | |||
---|---|---|---|
— no events scheduled — |
Friday, 21 July | |||
---|---|---|---|
— no events scheduled — |