BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2// METHOD:PUBLISH X-WR-CALNAME;VALUE=TEXT:Eventi DIAG BEGIN:VTIMEZONE TZID:Europe/Paris BEGIN:STANDARD DTSTART:20151025T030000 TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET END:STANDARD BEGIN:DAYLIGHT DTSTART:20150329T020000 TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT UID:calendar.7080.field_data.0@www.ugov-ricerca.uniroma1.it DTSTAMP:20260413T005659Z CREATED:20150615T040918Z DESCRIPTION:Algorithms Lunch-Time Talks@DIAG  Wednesday\, June 17th\, Aula Magna\, DIAG - Sapienza\, Via Ariosto 25 12:00 - 12:30  Solving Optimizati on Problems with Diseconomies of Scale via                              De coupling                       Maxim Sviridenko (Yahoo! Research NY)  12:3 0 - 13:00  Robust randomized matchings                        Jannik Matus chke (TU Berlin & Univ. of Tor Vergata)  13:00 - 14:00 Lunch break  14:00 - 14:30  Sequential Posted Price Mechanisms with Correlated Valuations                      Bart de Keijzer (Sapienza Univ. of Rome)  14:30 - 15:00  Parametric Network Flows                       Tom McCormick (Univ. of Br istish Columbia)  Abstracts:  Maxim Sviridenko (Yahoo! Research NY) Solvin g Optimization Problems with Diseconomies of Scale via Decoupling   We pre sent a new framework for solving optimization problems with a diseconomy o f scale. In such problems\, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly with the amount of resources used. We define a novel linear programming re laxation for such problems\, and then show that the integrality gap of the relaxation is A_q\, where A_q is the q-th moment of the Poisson random va riable with parameter 1. Using our framework\, we obtain approximation alg orithms for the Minimum Energy Efficient Routing\, Minimum Degree Balanced Spanning Tree\, Load Balancing on Unrelated Parallel Machines\, and Unrel ated Parallel Machine Scheduling with Nonlinear Functions of Completion Ti mes problems. (Joint work with Konstantin Makarychev)  Jannik Matuschke (T U Berlin & Univ. of Tor Vergata) Robust randomized matchings The following zero-sum game is played on a weighted graph: Alice selects a matching M a nd Bob selects a number k. Then\, Alice receives a payoff equal to the rat io of the weight of the k heaviest edges of M to the maximum weight of a m atching of size at most k in the graph. If M guarantees a payoff of at lea st L then it is called L-robust. In 2002\, Hassin and Rubinstein gave an a lgorithm that returns a sqrt(1/2)-robust matching\, which is best possible . In this talk\, we will see that Alice can improve on the guarantee of sq rt(1/2) when allowing her to play a randomized strategy. We devise a simpl e algorithm that returns a 1/ln(4)-robust randomized matching\, based on t he following observation: If all edge weights are integer powers of 2\, th en the lexicographically optimum matching is 1-robust. We prove this prope rty not only for matchings but for a very general class of independence sy stems that includes matroid intersection\, b-matchings\, and strong 2-exch ange systems. We also show that our robustness results for randomized matc hings translate to an asymptotic robustness guarantee for deterministic ma tchings: When restricting Bob's choice to cardinalities larger than a give n constant\, then Alice can find a single deterministic matching with appr oximately the same guaranteed payoff as in the randomized setting. (joint work with Martin Skutella and José A. Soto) Bart de Keijzer (Sapienza Univ . of Rome) Sequential Posted Price Mechanisms with Correlated Valuations A bstract: We study the revenue performance of sequential posted price (SPP) mechanisms when the valuations of the buyers are drawn from a correlated distribution. SPP mechanisms are conceptually simple mechanisms that work by proposing a 'take-it-or-leave-it' offer to each buyer. We apply SPP mec hanisms to settings in which each buyer has unit demand and the mechanism can assign the service to at most k of the buyers. We prove that with the valuation distribution having finite support\, no SPP mechanism can extrac t a constant fraction of the optimal expected revenue\, even with unlimite d supply. We prove that a better revenue performance can be achieved if th e SPP mechanism can for any buyer either propose an offer or ask for its v aluation. In this case\, a Omega(1/max{1\,d}) fraction of the optimal reve nue can be extracted\, where d is the degree of dependence of the valuatio ns\, ranging from independence (d = 0) to complete dependence (d = n − 1). We also show that to achieve a constant fraction of the optimal revenue\, it is sufficient to restrict to mechanisms making take-it-or-leave-it off ers in a sequence independent from the buyers' valuations. (joint work wit h Marek Adamkzyk\, Allan Borodin\, Diodato Ferraioli and Stefano Leonardi)   Tom McCormick (Univ. of Bristish Columbia) Parametric Network Flows We r eview the parametric optimization framework of Topkis\, and how the parame tric min cut results of Gallo\, Grigoriadis\, and Tarjan fit into the fram ework.  This framework gives two main results: a Structural Property that min cuts are monotone in the parameter\, and an Algorithmic Property\, tha t one can compute all min cuts in the same time as solving the non-paramet ric problem.  Most applications of this framework in combinatorial optimiz ation are to 0-1 problems such as Min Cut.We extend these results to param etric capacity and parametric rewards versions of 'Max Reward Flow'\, a 'm ax' version of Min Cost Flow.  We prove that the Structural Property again holds\, and we adapt the Relax algorithm of Bertsekas to also get the Alg orithmic Property.  We further indicate how to extend the results to param etric Weighted Abstract Flow\, and to other problems. (joint work with Bri tta Peis and Jannik Matuschke)  DTSTART;TZID=Europe/Paris:20150617T120000 DTEND;TZID=Europe/Paris:20150617T120000 LAST-MODIFIED:20150616T111232Z LOCATION:DIAG - Via Ariosto 25\, Aula Magna SUMMARY:Algorihtms Lunch Talks@DIAG - Maxim Sviridenko (Yahoo! Research NY )\, Jannik Matuschke (TU Berlin & Univ. of Tor Vergata)\, Bart de Keijzer (Sapienza Univ. of Rome)\, Tom McCormick (Univ. of Bristish Columbia) URL;TYPE=URI:http://www.ugov-ricerca.uniroma1.it/node/7080 END:VEVENT END:VCALENDAR