Data dell'evento:

Wednesday, 17 June, 2015 - 12:00

Luogo:

DIAG - Via Ariosto 25, Aula Magna

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)

Descrizione

Algorithms Lunch-Time Talks@DIAG

12:00 - 12:30 Solving Optimization Problems with Diseconomies of Scale via Decoupling

12:30 - 13:00 Robust randomized matchings

13:00 - 14:00 Lunch break

14:00 - 14:30 Sequential Posted Price Mechanisms with Correlated Valuations

14:30 - 15:00 Parametric Network Flows

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)

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)

Sequential Posted Price Mechanisms with Correlated Valuations

(joint work with Marek Adamkzyk, Allan Borodin, Diodato Ferraioli and Stefano Leonardi)

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)

Contatto:

Stefano Leonardi