Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing

Elfarouk Harb, Kent Quanrud, Chandra Chekuri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Boob et al. [7] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Qaunrud and Torres [10] extended the algorithm to supermodular density problems (of which DSG is a special case) and proved that the resulting algorithm Super-Greedy++ (and hence also Greedy++) converges. In this paper we revisit the convergence proof and provide a different perspective. This is done via a connection to Fujishige’s quadratic program for finding a lexicographically optimal base in a (contra) polymatroid [18], and a noisy version of the Frank-Wolfe method from convex optimization [17, 25]. This yields a simpler convergence proof, and also shows a stronger property that Super-Greedy++ converges to the optimal dense decomposition vector, answering a question raised in Harb et al. [24]. A second contribution of the paper is to understand Thorup’s work on ideal tree packing and greedy tree packing [46, 47] via the Frank-Wolfe algorithm applied to find a lexicographically optimum base in the graphic matroid. This yields a simpler and transparent proof. The two results appear disparate but are unified via Fujishige’s result and convex optimization.

Original languageEnglish (US)
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772952
DOIs
StatePublished - Sep 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: Sep 4 2023Sep 6 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume274
ISSN (Print)1868-8969

Conference

Conference31st Annual European Symposium on Algorithms, ESA 2023
Country/TerritoryNetherlands
CityAmsterdam
Period9/4/239/6/23

Keywords

  • Polymatroid
  • densest subgraph
  • lexicographically optimum base
  • tree packing

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing'. Together they form a unique fingerprint.

Cite this