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.diag.uniroma1.it
DTSTAMP:20240615T052949Z
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:https://www.diag.uniroma1.it/node/7080
END:VEVENT
END:VCALENDAR