Algorihtms Lunch Talks@DIAG
Speaker:
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)
Data dell'evento:
Wednesday, 17 June, 2015 - 12:00
Luogo:
DIAG - Via Ariosto 25, Aula Magna
Contatto:
Stefano Leonardi
Algorithms Lunch-Time Talks@DIAG
Wednesday, June 17th, Aula Magna, DIAG - Sapienza, Via Ariosto 25
12:00 - 12:30 Solving Optimization Problems with Diseconomies of Scale via Decoupling
Maxim Sviridenko (Yahoo! Research NY)
12:30 - 13:00 Robust randomized matchings
Jannik Matuschke (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 Bristish Columbia)
Abstracts:
Maxim Sviridenko (Yahoo! Research NY)
Solving Optimization Problems with Diseconomies of Scale via Decoupling
We present a new framework for solving optimization problems with a diseconomy of 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 relaxation 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 variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems.
(Joint work with Konstantin Makarychev)
Jannik Matuschke (TU Berlin & Univ. of Tor Vergata)
Robust randomized matchings
The following zero-sum game is played on a weighted graph: Alice selects a matching M and Bob selects a number k. Then, Alice receives a payoff equal to the ratio of the weight of the k heaviest edges of M to the maximum weight of a matching of size at most k in the graph. If M guarantees a payoff of at least L then it is called L-robust. In 2002, Hassin and Rubinstein gave an algorithm 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 sqrt(1/2) when allowing her to play a randomized strategy. We devise a simple algorithm that returns a 1/ln(4)-robust randomized matching, based on the following observation: If all edge weights are integer powers of 2, then the lexicographically optimum matching is 1-robust. We prove this property not only for matchings but for a very general class of independence systems that includes matroid intersection, b-matchings, and strong 2-exchange systems. We also show that our robustness results for randomized matchings translate to an asymptotic robustness guarantee for deterministic matchings: When restricting Bob's choice to cardinalities larger than a given constant, then Alice can find a single deterministic matching with approximately 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
Abstract: 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 mechanisms 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 extract a constant fraction of the optimal expected revenue, even with unlimited supply. We prove that a better revenue performance can be achieved if the SPP mechanism can for any buyer either propose an offer or ask for its valuation. In this case, a Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d is the degree of dependence of the valuations, 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 offers in a sequence independent from the buyers' valuations.
(joint work with Marek Adamkzyk, Allan Borodin, Diodato Ferraioli and Stefano Leonardi)
Tom McCormick (Univ. of Bristish Columbia)
Parametric Network Flows
We review the parametric optimization framework of Topkis, and how the parametric min cut results of Gallo, Grigoriadis, and Tarjan fit into the framework. This framework gives two main results: a Structural Property that min cuts are monotone in the parameter, and an Algorithmic Property, that one can compute all min cuts in the same time as solving the non-parametric problem. Most applications of this framework in combinatorial optimization are to 0-1 problems such as Min Cut.
We extend these results to parametric capacity and parametric rewards versions of "Max Reward Flow", a "max" 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 Algorithmic Property. We further indicate how to extend the results to parametric Weighted Abstract Flow, and to other problems.
(joint work with Britta Peis and Jannik Matuschke)