This is the calendar of the weekly Seminar S (until summer 2016 we meet at 2600 room 428, on Wednesdays at 14:00)
Next seminar: Wednesday May 25, 2016
Kim Thang Nguyen (Evry University)Online PrimalDual Algorithms with Configuration Linear Programs
Abstract
Abstract: In the talk, we present a primaldual approach based on configuration linear programs to design competitive online algorithms. Prior to our work, configuration linear programs have been considered only in offline setting and the main approaches are rounding techniques that have their limit due to the exponential size of configuration formulations. Instead, we consider a primaldual approach that first consists to strengthen natural linear programs by introducing exponential number of variables and constraints to reduce the integrality gap. Then, at any time, the algorithm maintains a primal feasible solution and a dual feasible solution for exponential number of dual constraints. The dual feasibility is proved by the mean of a new notion, called smoothness. The smoothness notion also allows us to characterize the competitiveness of online algorithms in our approach. Building upon our approach, we present competitive algorithms for a generalized network design problem and a energy minimization scheduling problem. These problems capture several extensively studied ones, such as Cost Distance, BuyatBulk, Energy Efficient Network Routing, etc. For these concrete problems, our algorithms are optimal (up to a constant factor) in online setting and also have the currently best approximation guarantees in offline setting.
Past seminars (Academic year 20152016)

Martin Hoeffer (Max Planck Institute for Computer Science)
Monday April 18, 2016
Abstract
This talk surveys some of our recent work on revealed preference problems in classic market models without information about the number of agents, their individual utilities and endowments. Here we only rely on queries that return aggregate demand for goods in order to, e.g., learn utility functions or compute a market equilibrium. As a main result, we design a simple ascendingprice algorithm to compute a (1+eps)approx. equilibrium in exchange markets with weak gross substitute (WGS) property. It runs in time polynomial in market parameters and log(1/eps). It represents the first efficient algorithm for this broad class of markets which is easy to implement and avoids heavy machinery such as the ellipsoid method. Moreover, we show how to broaden our approach to other classes of markets, in which we obtain the first efficient algorithms to compute exact equilibria.

Thomas Lidbetter (London School of Economics)
Wednesday April 6, 2016
Submodular search and scheduling
Abstract
We present a search problem in which an object is hidden in one of a finite number of locations according to a known probability distribution and must be found in minimal expected cost. The cost of searching a set of locations is assu$ This is joint work with Robbert Fokkink.

Safia KedadSidhoum (UPMC)
Wednesday March 30, 2016
Justintime scheduling with unavailability constraints
Abstract
We address a onemachine earlinesstardiness scheduling problem where a job cannot be executed in some time intervals called breaks. A job can start before and end after a break assuming an increase (or not) of its processing time. Preemption is only allowed if it occurs on a break. Each job has a due date and the objective is to minimize the total earliness and tardiness penalties. We will present a complexity analysis as well as exact solving methods based on some structural properties of the optimal solutions for some specific cases such as the common duedate, resumable and nonresumable cases. Joint work with Kerem Bulbul and Halil Sen.

Bruno Escoffier (UPMC)
Wednesday March 16, 2016
Parameterized power vertex cover
Abstract
We consider a generalization of the vertex cover problem, called power vertex cover. Each edge e=(u,v) has a weight w_e; we want to attribute a power p_u to each vertex u in order to cover all edges, while minimizing the sum of the $ We investigate to what extend classical parameterized results for vertex cover can be generalized to this power vertex cover problem, in particular results dealing with standard parameterization, treewidth and kernels.

Dimitri Watel (CNAM)
Wednesday March 9, 2016
Mutualisation de taxis avec partage de coût : modélisation, complexité et linéarisation du problème
Abstract
On se propose dans cette présentation d’étudier une variante du problème DialARide (DARP). Dans, le problème original, on cherche à optimiser les routes de véhicules chargés de transporter des personnes depuis leurs origines respectives vers leurs destinations respectives, tout en respectant des contraintes de fenêtre de temps et des contraintes de capacités (nombre de places dans le véhicule). Ce modèle est généralement utilisé pour optimiser des chemins pour des taxis. Nous nous penchons sur une variante de ce problème dans laquelle les clients partagent le coût des trajets (ou des parties de trajets) qu'ils effectuent avec d'autres clients. Nous étudions dans un premier temps la complexité de ce problème. Puis, nous présentons un modèle linéaire en variable mixte et des règles de réduction de l'instance. La présentation se termine par une présentation des résultats de tests numériques.

Christoph Durr (CNRSUPMC)
Wednesday March 2nd, 2016
The triangle scheduling problem
Abstract
We introduce a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the \emph{binary tree ratio}. It is shown that the greedy algorithm solves the problem to optimality when the binary tree ratio is at most 2. We also show that the problem is unary NPhard for instances with binary tree ratio strictly larger than 2, and provide a quasi polynomial time approximation scheme (QPTAS). The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05. joint work with Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez and Gerhard Woeginger,

Shikha Singh (Stony Brook University)
February 3rd, 2016
Run Generation Revisited: Competitive Analysis of Online and Offline Sorting with a Buffer
Abstract
In this talk, we will revisit the classic problem of run generation. Run generation is the first phase of externalmemory sorting, where the objective is to scan through the input of size N, reorder elements using a small buffer of siz$ We develop algorithms for minimizing the total number of runs (or equivalently, maximizing the average run length) when the runs are allowed to be sorted or reverse sorted. We study the problem in the online setting, both with and with$ We show that the simple strategy of alternating between sorted and reverse sorted runs, which was also studied by Knuth as far back as 1963, is asymptotically optimal. Specifically, we show that it is 2competitive and no deterministic$

ChienChung Huang (Chalmers University)
January 28, 2016
Exact and Approximation Algorithms for Weighted Matroid Intersection
Abstract
We propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a $(1\epsilon)$approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1\epsilon)$approximate solution via solving $O(\epsilon^{1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.

Pierre Fouilhoux (UPMC)
December 11, 2015
Cellular inequalities for the bipartite induced subgraph polytope
Abstract
Given a graph G=(V,E) with node weights, the Bipartite Induced Subgraph Problem (BIS Problem) is to find a maximum weight subset of nodes W of G such that the subgraph induced by W is bipartite. The bipartite induced subgraph polytope is the convex hull of the incidence vectors of the node sets of all the induced bipartite subgraphs. We call cellular graphs the planar graphs with maximum node degree limited to three. We consider a large family of valid inequalities, called cellular inequalities. We first investigate the structure of the graphs producing the cellular inequalities. Then we discuss necessary conditions and sufficient conditions for these inequalities to be facet defining.

Dimitris Fotakis (National Technical University of Athens)
Who to Trust for Truthfully Maximizing Welfare?
November 17, 2015
Abstract
We introduce a general approach based on selective verification and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of utilitarian voting. Having a good allocation in mind, a mechanism with verification selects few critical agents and detects, using a verification oracle, whether they have reported truthfully. If yes, the mechanism produces the desired allocation. Otherwise, the mechanism ignores any misreports and proceeds with the remaining agents. We obtain randomized truthful (or almost truthful) mechanisms without money that verify only O(\ln m/\eps) agents, where m is the number of outcomes, independently of the total number of agents, and are (1\eps)approximate for the social welfare. We also show that any truthful mechanism with a constant approximation ratio needs to verify \Omega(\log m) agents. A remarkable property of our mechanisms is immunity, namely that their outcome depends only on the reports of the truthful agents. This is joint work with Christos Tzamos and Emmanouil Zampetakis.

SiaoLeu Phouratsamay (UPMC)
Problèmes de lotsizing à deux niveaux avec capacité de stockage limitée
November 5, 2015
Abstract
Nous étudions différents problèmes de lotsizing à deux niveaux (2ULS) avec capacité de stockage limitée. Ces problèmes interviennent dans les chaînes logistiques composées de deux acteurs: un fournisseur et un distributeur. Le distributeur doit satisfaire une demande externe sur un horizon de temps discret en déterminant un plan d'approvisionnement auprès du fournisseur. Puis, le fournisseur détermine un plan de production afin de satisfaire le plan d'approvisionnement du distributeur. Le problème 2ULS consiste à déterminer un plan d'approvisionnement et un plan de production en minimisant le coût total de la chaîne logistique. Lorsque le distributeur possède une capacité de stockage limitée, nous avons montré que le problème 2ULS peut être résolu en temps polynomial par un algorithme de programmation dynamique. Lorsque le fournisseur possède une capacité de stockage limitée, le problème 2ULS devient NPdifficile.

Nawal Benabbou (UPMC)
On possibly optimal trade offs in multicriteria spanning trees
October 9, 2015

Spyros Angelopoulos (CNRSUPMC)
Further connections between contract scheduling and ray searching problems
October 2, 2015
Abstract
In this presentation we address connections between two classes of different, yet interrelated optimization problems. The first class of problems involves a searcher that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We discuss several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and faulttolerance issues, randomized strategies, and tradeoffs between performance and preemptions. For many of these problems we present the first known results that apply to multiray and multiproblem domains. Our objective is to demonstrate that several wellmotivated settings can be addressed using the same underlying approach.

Christoph Dürr (CNRSUPMC)
Fast shortest paths in weighted connected graphs
September 25, 2015