Réunion du groupe Algorithmique à Garantie de Performance

Programme de la Réunion du GT Algorithmique à Garantie de Performance

Date : 6 juin 2014
Lieu : LIP6, Jussieu, 1er étage, couloir 25-26, salle 105

9h30-10h00 : Accueil de participants-café

10h00-10h30 : Eduard Bonnet, LAMSADE
10h30-11h00 : Maryam Seifeddini, LCOMS

11h00-11h15 : Pause

11h15-11h45 : Annie Chateau, LIRMM
11h45-12h15 : Lydia Tlilane, LAMSADE

12h15-14h00 : Repas

14h00-14h30 : Guillerme Duvillié, LIRMM
14h30-15h00 : Vincent Chau, IBISC et LIP6
15h00-15h30 : Georgios Zois, Athens University of Economics and Business and LIP6

15h30-16h00 : Discussion

Résumés

Eduard Bonnet, LAMSADE

Parameterized complexity of cardinality-constraint problems in bipartite graphs

Optimization cardinality-constraint (that is where the solution should be a subset of k vertices) graph problems are usually W[1]-hard. This is the case for min and max k-vertex cover, k-densest, k-sparsest, min and max (k,n-k)-cut. We show the surprising result that, in bipartite graphs, max k-vertex cover and max (k,n-k)-cut are FPT while both minimization versions remain W[1]-complete.

Maryam Seifeddini, LCOMS

Efficient Approximation Schemes for the Maximum Lateness Minimization on a Single Machine with a Fixed Operator or Machine Non-Availability Interval

Résumé :

We consider the single machine scheduling problem with one non-availability interval to minimize the maximum lateness where jobs have positive tails. Two cases are considered. In the first one, the non-availability interval is due to the machine maintenance. In the second case, the non-availibility interval is related to the operator who is organizing the execution of jobs on the machine. Our contribution consists in an improved FPTAS for the maintenance non-availability interval case and the elaboration of the first FPTAS for the operator non-availability interval case. The two FPTAS are strongly polynomial.

Annie Chateau, LIRMM

Complexity and Polynomial-Time Approximation Algorithms around
the Scaffolding Problem

Résumé : We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP-complete, even in bipartite graphs. We also exhibit non-approximability and polynomial-time approximation results, in the optimization versions of the problem.

Lydia Tlilane, LAMSADE

Solutions de compromis pour des matroïdes pondérés coloriés.

Résumé :
Nous considérons des problèmes d'optimisation où chaque solution réalisable est évaluée par un couple. Chaque coordonnée du couple représente l'utilité d'un agent. L'une de ces deux utilités est additive et l'autre est une fonction sous-modulaire particulière appelée le « prix chromatique ». L'objectif consiste à déterminer une solution de compromis pour ces deux agents avec une garantie dans le pire cas sur l'utilité de chacun. Les problèmes considérés sont de nature combinatoire. Plus précisément, il s’agit de la classe des systèmes d’ensembles qui ont une structure de matroïde. La théorie des matroïdes est centrale en optimisation combinatoire, elle a permis d’unifier des structures apparemment séparées comme les forêts et les couplages dans les graphes et elle a engendré des algorithmes efficaces pour résoudre des problèmes d’optimisation non triviaux en temps polynomial. Nous proposons des algorithmes déterministes polynomiaux avec garantie de performance pour différentes variantes du problème et nous montrons que certaines garanties ne sont pas possible à atteindre.

Guillerme Duvillié, LIRMM

On the complexity of the Wafer to Wafer Integration problem.

Abstract

The wafer to wafer integration problem is motivated by Microelectronics. We aim at conceiving 3-dimensional processors by empiling wafers and then by creating a stack. A wafer contains p dies, and is represented by a binary p-dimensional vector, such that the i^th component is equal to 1 if and only if the corresponding die is a viable one. The stack resulting in the assignment of many wafers is also a p-dimensional vector. In the latter, the i^th component is equal to 1 if and only if the i^th component of every vector composing the stack is equal to 1. In other words, we perform a logical *and* operation on the composing vectors. Thus the objective is now to find an assignment on the vector such that the resulting stacks contains a maximal number of 1. In this presentation we address the approximability of the problem in reference with p. We present inapproximability results via gap reduction and approximation algorithms using dynamic programing and linear programing.

Vincent Chau, IBISC et LIP6

Maximisation de profit dans les systèmes informatiques sous contraintes énergétiques

Résumé

L'économie d'énergie dans les systèmes informatiques est aujourd'hui un sujet très important aussi bien du point de vue écologique qu'économique. Dans ce contexte, on considère le problème d'ordonnancement suivant : étant donné un ensemble de tâches et un processeur qui peut varier sa vitesse dynamiquement, l'objectif est d'exécuter un maximum de tâches sans dépasser le budget sur l'énergie. Chaque tâche est caractérisée par sa quantité de travail, sa date de relâchement et sa date d'échéance. Bien que le problème de la minimisation d'énergie ait été résolue en temps polynomial [Yao et al., FOCS'95], la complexité du problème de la maximisation du nombre de tâches exécutées reste ouverte. On répond partiellement à cette question en proposant un algorithme de programmation dynamique qui résout le problème en temps pseudo-polynomial. Notre algorithme peut être adapté pour le cas pondéré dans lequel chaque tâche est associée à un poids et où l'objectif est de maximiser la somme des poids des tâches exécutées.

Georgios Zois, Athens University of Economics and Business and LIP6

Scheduling MapReduce Jobs on Unrelated Processors

Abstract

MapReduce framework has been established as the standard approach for parallel processing of massive amounts of data. In this work, we extend the model of MapReduce scheduling on unrelated processors (Moseley et al., SPAA 2011) and deal with the practically important case of jobs with any number of Map and Reduce tasks. We present a polynomial-time $(32+\epsilon)$-approximation algorithm for minimizing the total weighted completion time in this setting. To the best of our knowledge, this is the most general setting of MapReduce scheduling for which an approximation guarantee is known.