<div dir="ltr"><div>Seminari di Matematica Applicata, Dipartimento di Matematica &quot;F. Casorati&quot; e Istituto del CNR IMATI &quot;E. Magenes&quot; di Pavia.<br><br>Martedì 29 novembre 2022, alle ore 15.00 precise, presso l&#39;aula Beltrami del Dipartimento di Matematica,<br><br><h4 style="padding:0px;margin:0px 0px 10px;clear:none;color:rgb(23,28,36);font-weight:300;font-stretch:normal;line-height:1.2;font-family:Montserrat,-apple-system,BlinkMacSystemFont,&quot;Segoe UI&quot;,Roboto,sans-serif;box-sizing:border-box"><font size="4">Yuri Faenza (Columbia University)</font></h4><h4 style="padding:0px;margin:0px 0px 10px;clear:none;color:rgb(23,28,36);font-weight:300;font-stretch:normal;line-height:1.2;font-family:Montserrat,-apple-system,BlinkMacSystemFont,&quot;Segoe UI&quot;,Roboto,sans-serif;box-sizing:border-box"><br></h4>terrà un seminario dal titolo:<br><br><h3 style="padding:0px;margin:5px 0px 8px;clear:none;color:rgb(23,28,36);font-weight:300;font-stretch:normal;line-height:1.2;font-family:Montserrat,-apple-system,BlinkMacSystemFont,&quot;Segoe UI&quot;,Roboto,sans-serif;box-sizing:border-box"><font size="4">Incremental knapsack problems.</font></h3></div><div><font size="4"><br></font></div><div>Il seminario verrà anche trasmesso in diretta su zoom al link<br><div><br></div><div>Link Zoom:<span class="gmail-Apple-converted-space"> </span><a href="https://us02web.zoom.us/j/83344185446?pwd=RHRGai91RkZQTjg0eEVRMWQ5WXFjZz09" target="_blank">https://us02web.zoom.us/j/83344185446?pwd=RHRGai91RkZQTjg0eEVRMWQ5WXFjZz09</a><font color="#888888"><br clear="all"></font></div><div><br></div><div><span style="color:rgb(61,61,61);font-family:Roboto,sans-serif">Abstract. </span></div><div><span style="color:rgb(61,61,61);font-family:Roboto,sans-serif;font-size:14px">In this talk, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. We will mostly focus on incremental versions of the classical knapsack. In such models, we are given an added time component and weakly increasing capacities for each time, as to mimic the increase in available resources. Items can be inserted at any time, but once an item is inserted, it cannot be removed in future times. The goal is to maximize some item-dependent, and possibly also time-dependent, objective function under such constraints. We will present algorithms that perform well in theory and/or in practice for incremental knapsack problems and their extensions.</span><br style="padding:0px;margin:0px;box-sizing:border-box;color:rgb(61,61,61);font-family:Roboto,sans-serif;font-size:14px"><p style="padding:0px;margin:0px 0px 20px;box-sizing:border-box;color:rgb(61,61,61);line-height:23px;font-stretch:normal;font-family:Roboto,sans-serif"><span style="font-size:14px">Based on joint work with Danny Segev (Tel Aviv) and Lingyi Zhang (Columbia-&gt; Uber).</span></p><p style="padding:0px;margin:0px 0px 20px;box-sizing:border-box;color:rgb(61,61,61);line-height:23px;font-stretch:normal;font-family:Roboto,sans-serif"><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">Short Bio: Yuri Faenza is an associate professor in the IEOR department at Columbia University. He works in discrete optimization, operations research, matching theory, and their applications. His research has been funded by the NSF (including an NSF Career award), the ONR, the Swiss NSF, and by a Meta Research Award.</span><span style="font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)"><br></span></p><p style="padding:0px;margin:0px 0px 20px;box-sizing:border-box;color:rgb(61,61,61);line-height:23px;font-stretch:normal;font-family:Roboto,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)">---------------------</span></p></div></div><div>Pagina web dei Seminari di Matematica Applicata<br><a href="https://matematica.unipv.it/ricerca/cicli-di-seminari/seminari-di-matematica-applicata/" rel="noreferrer" target="_blank">https://matematica.unipv.it/ricerca/cicli-di-seminari/seminari-di-matematica-applicata/</a></div></div>