Mini-workshop on Algorithms

Date: 7th June 2019

Place: Tour 26 – 1er étage – couloir 25/26 – salle 105
Sorbonne université
4 place de Jussieu, Paris (métro Jussieu)

Program

14h30: On a generalization of iterated and randomized rounding
Nikhil Bansal, professor, TU Eindhoven, The Netherlands
Abstract: I will describe a new method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems such as makespan minimization on unrelated machines, degree-bounded spanning trees and rounding column-sparse LPs.

15h30: Online Algorithms via Projections
Seffi Naor, professor, Technion, Israel
Abstract: We present a new/old approach to the design of online algorithms via Bregman projections. This approach is applicable to a wide range of online problems and we discuss connections to previous work on online primal-dual algorithms. In particular, the k-server problem on trees and HSTs is considered. The projection-based algorithm for this problem turns out to have a competitive ratio that matches some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm uses mirror-descent-based continuous dynamics prescribed via a differential inclusion.
Joint work with Niv Buchbinder, Anupam Gupta, and Marco Molinaro.

16h30: Envy-free division of a cake: the poisoned case, and other variations
Frédéric Meunier, researcher, Ecole des Ponts, France
Abstract: Given a cake (identified with the interval [0,1]) and players with different tastes, the envy-free cake-cutting problem asks for a partition of the cake into connected pieces so that it is possible to assign the pieces to the players without making any of them jealous. The Stromquist-Woodall theorem ensures the existence of such an envy-free division under mild conditions. Recently, Segal-Halevi asked whether these conditions could be even further relaxed by allowing that some players dislike the cake (e.g., they know the cake has been poisoned). In the traditional setting, all players are "hungry", and always prefer to get something instead of nothing. We provide a partial answer to that question and propose also other extensions, e.g., when suddenly one player disappears.
Based on joint work with Florian Frick, Kelsey Houston-Edwards, Francis E. Su, Shira Zerbib.