var sms = '<div id="sms_bulletin">  <div id="sms_header">  <div class="do_not_print" id="arrow_left"><a href="?next=-54"><img src="//www2.math.ethz.ch/smsjs/images/arrow_left.png"/></a></div><div class="do_not_print" id="arrow_right"><a href="?next=-52"><img src="//www2.math.ethz.ch/smsjs/images/arrow_right.png"/></a></div>    <div class="sms_title">      <span style="float: left;">SMS</span>      <span>SWISS MATHEMATICAL SOCIETY</span>      <span style="float: right;">SMG</span>    </div>    <div class="sms_info">      <span style="float: left; width: 250px;">Bulletin no. 7</span>      <span style="float: right; text-align:right; width: 250px;">17.7 - 21.7.2023</span>      <span style="text-align: center; display: block; width: 250px; margin: auto; position: relative;">Summer Break 2023</span>    </div>  </div>  <div></div>  <div id="sms_content">    <div class="day">      <div class="day_title">        Monday, July 17      </div>      <div class="day_content">        <div class="day_content_item no_event">        No events scheduled today!        </div>      </div>    </div>    <div class="day">      <div class="day_title">        Tuesday, July 18      </div>      <div class="day_content">        <div class="day_content_item normal"><div class="event_location uni_zh"><a class="external" href="https://ethz.ch">ETH Z&uuml;rich</a></div><div class="event_type"><a class="external" href="https://math.ethz.ch/s/daco-seminar">DACO Seminar</a></div><br /><div class="event_speaker"><a class="external" href="https://chekuri.cs.illinois.edu/">Prof. Dr. Chandra Chekuri (University of Illinois at Urbana-Champaign)</a></div><div class="event_title">Densest Subgraph: Supermodularity and Iterative Peeling <span class="abstract-button do_not_print">abstract</span></div><div class="abstract-text" style="display: none"><strong>Abstract:</strong><br />The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirectedgraph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the setof edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practiceand have several applications in data mining and network analysis. We study fast algorithms andstructural aspects of DSG via the lens of supermodularity. For this we consider the densest supermodularsubset 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 forDSS 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 aconjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact provethat a natural generalization of their algorithm converges for DSS. In subsequentwork 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 basein a (contra) polymatroid, and continuous optimization algorithms such Frank-Wolfe method and MultiplicativeWeight Updates.Based on joint work in papers with Harb El Farouk, Kent Quanrud and Manuel Torres.</div><div class="event_time">13:15 &bull; ETH Zentrum, R&auml;mistrasse 101, Z&uuml;rich, Building HG, Room G 19.2</div>        </div>      </div>    </div>    <div class="day">      <div class="day_title">        Wednesday, July 19      </div>      <div class="day_content">        <div class="day_content_item no_event">        No events scheduled today!        </div>      </div>    </div>    <div class="day">      <div class="day_title">        Thursday, July 20      </div>      <div class="day_content">        <div class="day_content_item no_event">        No events scheduled today!        </div>      </div>    </div>    <div class="day">      <div class="day_title">        Friday, July 21      </div>      <div class="day_content">        <div class="day_content_item no_event">        No events scheduled today!        </div>      </div>    </div>  </div>  <div id="sms_footer">    address: Alessandra Naldi Windler, Departement Mathematik, HG G 51.4, ETH Zurich, Raemistrasse 101, CH-8092 Zurich<br />    email: <a href="mailto:bulletin@math.ch">bulletin@math.ch</a> | phone: +41 44 632 3684 | url: <a href="https://math.ch">https://math.ch</a>    <br /><br /><img src="//www2.math.ethz.ch/smsjs/sms_logo.gif" width="150" alt="SMS/SMG Logo" title="SMS/SMG Logo" />  </div></div>';