{"654516":{"#nid":"654516","#data":{"type":"event","title":"ARC Colloquium: Chandra Chekuri (Univ. of Illinois) ","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EChandra Chekuri (Univ. of Illinois) \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 11, 2022\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003EDensest Subgraph: Supermodularity, Iterative Peeling, and Flow\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EThe 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 many 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|.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFor DSG we describe a simple flow-based algorithm that outputs a (1\u0026minus;\\epsilon)-approximation in deterministic O(m polylog(n)\/\\epsilon) time where m is the number of edges.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGreedy 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 any supermodular function f; the key to our proof is to consider an LP formulation that is derived via the Lov\u0026aacute;sz extension of a supermodular function which is inspired by the LP relaxation of Charikar that has played an important role in several developments.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Kent Quanrud and Manuel Torres.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/chekuri.cs.illinois.edu\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003Cem\u003E and\u0026nbsp;\u003C\/em\u003E \u003Cem\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Densest Subgraph: Supermodularity, Iterative Peeling, and Flow - Klaus 1116 East at 11am"}],"uid":"27544","created_gmt":"2022-01-18 19:53:19","changed_gmt":"2022-03-24 15:14:06","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-04-11T12:00:00-04:00","event_time_end":"2022-04-11T13:00:00-04:00","event_time_end_last":"2022-04-11T13:00:00-04:00","gmt_time_start":"2022-04-11 16:00:00","gmt_time_end":"2022-04-11 17:00:00","gmt_time_end_last":"2022-04-11 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}