Presentations2014-2015.

jeudi 25 juin 2015 (attention, jour inhabituel), 14h, C516 : Riccardo Dondi (Bergamo, Italy). Gene Tree Editing for Reconciliation.

Reconciliation consists in mapping a gene tree into a
species tree in order to explain the incongruence between the two as
evidence for duplications, losses or other evolutionary events.
As reconciliation is very sensitive to errors in gene trees,
correction prior to reconciliation is a fundamental task. In this
talk, we will consider three different combinatorial approaches to
gene tree correction, based on edit operations
(deletion, modification and insertion) on leaves of the gene tree.
We will discuss some results for the computational, parameterized and
approximation complexity for three problems arising in this context.

8 juin 2015, 14h, C 131 : Cédric Bentz (CEDRIC, CNAM). Steiner trees with edge capacities.

Assume we are given a graph G=(V,E) (directed or not) with
capacities and costs on the edges, a vertex r of G called root, and a set
X of terminal vertices. The problem we consider is the following : find in
G a minimum-cost tree rooted at r, spanning all the vertices in X, and
such that, for each edge of this tree, the number of paths going from r to
terminals and containing this edge does not exceed its capacity. When all
capacities are at least |X|, then this is the classical Steiner tree
problem, with a given root. The generalization we are interested in has
several relevant applications, including the design of wind farm
collection networks. We study the complexity of this problem in different
settings : for instance, the graph may be directed or not, |X| may be fixed
or not, the costs may be 0 or not. Whenever this is possible, we also
design approximation algorithms to solve the problem.

1 juin 2015, 14h, A711 : Ioannis Caragiannis (Department of Computer Engineering & Informatics, Patras, Greece). Computing approximate equilibria in constraint satisfaction games

Abstract : We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al. (EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler. En route, we will discuss applications of these techniques to congestion games and present many open problems.

Joint work with Angelo Fanelli and Nick Gravin

26 mai 2015 (jour inhabituel), 14h, A711. Zoltan Szigeti (G-Scop Grenoble). Old and new results on packing arborescences.

As the title suggests, I will present old and new results on packing of arborescences.
The new results are about packings of arborescences in directed hypergraphs with matroid constraints.

11 mai 2015, 14h, C110 : Ivana Ljubic (Department of Statistics and Operations Research, Vienna). MIP Approaches to the Lazy Bureaucrat and Greedy Boss Problems.

Abstract : Lazy reformulations of classical combinatorial optimization problems are new and challenging classes of problems. In this talk I will focus on the Lazy Bureaucrat Problem (LBP) which is the lazy counterpart of the knapsack problem. Given a set of tasks with a common arrival time and deadline, the goal of a lazy bureaucrat is to schedule a least profitable subset of tasks, while having an excuse that no other tasks can be scheduled without exceeding the deadline.

Three ILP formulations and their CP counterparts are studied and implemented. In addition, a dynamic programming algorithm that runs is pseudo-polynomial time and polynomial greedy heuristics are implemented and computationally compared with ILP/CP approaches. For the computational study, a large set of knapsack-type instances with various characteristics is used to examine the applicability and strength of the proposed approaches.

In the second half of my talk I will also address a game-theoretical counterpart of the LBP, called the Greedy Boss Problem.

Joint work with Fabio Furini, Paris Dauphine and Markus Sinnl, University of Vienna

4 mai 2015, 14h, P303 : Daniel Paulusma (Durham University). Clique-width of Hereditary Graph Classes.
Slides

Joint work with Andreas Brandstadt, Konrad Dabrowski and Shenwei Huang

Abstract : Clique-width is a well-known graph parameter, studied both in a structural and in an algorithmic context. However, our understanding of clique-width is still limited. For example, no polynomial-time algorithms are known for computing the clique-width of very restricted graph classes, such as unit interval graphs, or for deciding whether a graph has clique-width at most c for any fixed c>=4. In order to get more structural insight into clique-width, we are interested in determining whether the clique-width of some given class of graphs is bounded, that is, whether there exists a constant c such that every graph from the class has clique-width at most c. In this talk we focus on classes of graphs characterized by a number of forbidden induced subgraphs and describe a number of techniques for determining whether their clique-width is bounded or unbounded. In particular we present results for H-free bipartite graphs, H-free split graphs, H-free chordal graphs and (H1,H2)-free graphs.

27 mars 2015, 11h (attention, horaire et jour inhabituels), A709 : Paolo Toth (University of Bologna). A Reduced-Cost Iterated Local Search Heuristic for the Fixed Charge Transportation Problem

The Fixed Charge Transportation Problem (FCTP) is a generalization of the Transportation Problem where an additional fixed cost is paid for sending a flow from an origin to a destination. We propose an Iterated Local Search heuristic based on the utilization of reduced costs for guiding the restart phase. The reduced costs are obtained by applying a lower bounding procedure that computes a sequence of non-decreasing lower bounds by solving a three-index mathematical formulation of the problem strengthened with valid inequalities. The proposed method was tested on the sets of benchmark instances from the literature. The proposed heuristic was able to provide, within short computing times, new best-known solutions on all the considered instances.

23 mars 2015, 14h, A711 : Claire Mathieu (ENS). Graph reconstruction and verification via distance oracles .

We study the problem of reconstructing a hidden graph, which can only be accessed by querying pairs of vertices and getting their shortest path or their distance in the graph. We wish to design algorithms with small query complexity. We also study approximate reconstruction.
Further, we explore the verification problem, in which we are given a hypothetical graph and wish to verify that the graph is correct using few queries.
We make progress on those problems for graphs of bounded degree, outerplanar graphs, and graphs of bounded treewidth.

(Joint work with Hang Zhou and partly with Sampath Kannan)

16 mars 2015, 11h (attention, horaire inhabituel !), A 711 : Jannis Kurtz (Technische Universität Dortmund). Min-max-min robustness : a new approach to combinatorial optimization under uncertainty based on multiple solutions.

In the classical min-max approach to robust combinatorial optimization, a single feasible solution is computed that optimizes the worst case over a given set of considered scenarios. As is well known, this approach is very conservative, leading to solutions that in the average case are far from being optimal. We present a different approach : the objective is to compute k feasible solutions such that the best of these solutions for each given scenario is worst-case optimal, i.e., we model the problem as a min-max-min problem. In practice, these k solutions can be computed once in a preprocessing phase, while choosing the best of the k solutions can be done in real time for each scenario occuring. Using a polynomial-time oracle algorithm, we show that the problem of choosing k min-max-min optimal solutions is as easy as the underlying combinatorial problem if k is greater or equal n+1 and if the uncertainty set is a polytope or an ellipsoid. On contrary, in the discrete scenario case, many tractable problems such as the shortest path problem or the minimum spanning tree problem turn NP-hard in the new approach.

9 mars 2015, 14h, C 108 : Michel Habib (LIAFA). Diameter computations and graph algorithms for huge graphs.

I will first discuss the complexity issues of the graph diameter problem and its relationships with other well-known graph problems.

Then I will present some recent exact an efficient algorithms to compute diameter of huge graphs. These algorithms are based on graph searches and I will develop some theoretical aspects of graph searches.

To conclude I will propose a new graph based heuristics for community detection on huge graphs and explain how it can be used in a biological problem.

26 janvier 2015, 14h. P 516 : Hassene Aissi (LAMSADE). Strongly polynomial bounds for multiobjective and
parametric global minimum cuts.

We consider multiobjective and parametric versions of the global
minimum cut problem in undirected graphs and bounded-rank hypergraphs,
where each edge is evaluated by several cost functions. For a fixed number
of edge cost functions, we show that the total number of supported nondominated
(SND) cuts does not exceed an upper bound which is a polynomial
in the numbers of nodes and edges, i.e., a strongly polynomial bound.
This bound also applies to the number of linear pieces of the parametric curve
(facets of the epigraph) for the scalarized (linear combination) objective over
the set of all parameter vectors such that the parametrized edge costs are
nonnegative and the parametrized cut costs are positive. We refine this bound
in the case of two objectives (bicriteria problem), for which we also derive
a strongly polynomial upper bound on the total number of non-dominated
(Pareto efficient) cuts. In particular, the bicriteria global minimum cut problem
in an n-node graph admits O(n3) SND cuts and O(n7) non-dominated
(Pareto efficient) cuts. These results significantly improve on earlier graph cut
results by Mulmuley (1999) and Armon and Zwick (2006). They also imply
that the parametric curve and all SND cuts, and, for the bicriteria problems,
Pareto efficient cuts, can be computed in strongly polynomial time when the
number of objectives is fixed. Joint work with A. Ridha Mahjoub,
S. Thomas McCormick, and Maurice
Queyranne.

19 janvier 2015, 14h. P 516 : Laurent Gourvès (LAMSADE). Coupons des matroïdes comme des gâteaux.
Slides

On s’intéresse au partage équitable de biens indivisibles et leur extension aux matroïdes. En particulier on cherche des bornes inférieures sur l’utilité de l’agent le plus pauvre, dans le pire des cas. Ces bornes peuvent être obtenues par le biais d’un algorithme centralisé ou d’un protocole décentralisé s’inspirant du fameux protocole "cut and choose". Travail effectué avec J. Monnot et L. Tlilane.

12 janvier 2015, 14h, A711 : Pauline Sarrabezolles (CERMICS). Aspects combinatoires de la programmation linéaire colorée..
Nous étudions des cas particuliers de programmation linéaire colorée correspondant à des problèmes dans des graphes (recherche de chemins, de circuits ou de flots arc-en-ciel). Nous nous intéressons principalement à la complexité de ces problèmes.
Etant donnée une partition A_1 ∪·s∪ A_k de A, un sous-ensemble T⊆ A est dit /arc-en-ciel/ s’il est tel que |T∩ A_i |≤ 1 pour tout i∈1,...,k. Soit *S*_1 ∪...∪*S*_d+1 ⊆*R*^d une partition de *S*⊆*R*^d . D’après le théorème de Carathéodory coloré, si chacun des *S*_i contient *0* dans sont enveloppe convexe, alors il existe un sous-ensemble arc-en-ciel T⊆*S* contenant lui aussi *0* dans son enveloppe convexe. Pour autant, le calcul de T est un problème dont on ne connaît pas la complexité.
La programmation linéaire colorée est définie en 1997 comme l’ensemble des problèmes liés au théorème de Carathéodory coloré, aussi bien ceux de calcul d’un ensemble arc-en-ciel que ceux d’existence sous des conditions plus générales. Je présenterai quelques résultats sur des versions combinatoires de la programmation linéaire colorée, obtenus au cours de collaborations avec Frédéric Meunier, Wolfgang Mülzer et Yannik Stein.

22 décembre 2014, 14h, salle A707 : Mounir Marrakchi (Université de Sfax, Tunisie). Ordonnancement parallèle optimal d’une anti-arborescence
à taches de durées égales dans un environnement hétérogène.

Dans ce travail nous présentons l’ordonnancement parallèle des tâches de
durées égales d’une anti-arborescence binaire et complète (CBT). Ce
graphe est obtenu en parallélisant une expression arithmétique dont
l’opérateur est associatif. Si l’on dispose d’un (CBT) de hauteur H et p
processeurs de vitesses différentes, nous décrivons une borne inférieure
du temps d’exécution des tâches de (CBT), sous certaines conditions,
et nous caractérisons l’ordonnancement optimal exécutant ce graphe.

(Mercredi) 17 décembre 2014 (16h), salle A707 (attention, date et horaire inhabituels) : Olivier Durand de Gevigney (Sauder school of Business, Vancouver). Orientation des graphes et connexité.
Slides

Le premier résultat d’orientation sous contrainte de connexité est le théorème de Robbins (1939). A partir de là nous pouvons distinguer deux branches. La première qui aborde les orientations sous contraintes d’arc-connexité commence avec le théorème de Nash-Williams (1960) et continue encore aujourd’hui dêtre développée. La deuxième branche, plus récente, traite des questions d’orientations relatives à la sommet-connexité. Elle commence avec la conjecture de Thomassen (1985) qui reste encore largement ouverte malgré quelques résultats encourageant.

8 décembre 2014 : Bernard Ries (LAMSADE), 14h, salle C110. On some graph modification problems related to graph parameters.
Slides

A graph modification problem is usually defined as follows. We fix a
graph class C and a set S of one or more graph operations. The input
consists of a graph G and an integer k. The question is whether G can be
modified into a graph H of the class C by using at most k operations from
S. Now, instead of fixing a particular graph class C, one may want to fix
a graph parameter p instead. Then the question becomes whether G can be
modified, by using at most k operations from S, into a graph H with p(H)
\leq p (G) - d for some threshold d, which is a non-negative integer that
can either be fixed or be part of the input. In this talk, we will present
results obtained by considering graph operations like for instance vertex
deletion, edge deletion and edge contraction and graph parameters like for
instance stability number, chromatic number and matching number.

(Mercredi) 3 décembre 2014 (Attention, date inhabituelle), 14h, salle C110 : Enrico Malaguti (Bologna). Nonlinear chance-constrained problems with applications to hydro scheduling.
Slides
Midterm hydro scheduling problem is about optimizing the performance of a
hydro network over a period of few months. This decision problem is
affected by uncertainty on energy prices, demands and rainfall, and we
model it as a nonlinear chance-constrained mathematical program. This is a
Multi-stage problem where at each stage we must decide how much water to
release from the reservoirs, i.e. determines how much energy we can
produce. The production function is nonlinear, at a first approximation
concave, but in fact nonconvex. Moreover, the inflows and the demands are
random, thus the profit over the entire time horizon is therefore
nondeterministic. We present a Branch-and-Cut algorithm based on the
approach recently pro- posed by Jim Luedtke, which uses Benders-type cuts.
However, in our case the feasible region induced by each scenario is a
general convex set instead of a polyhedron. Further more, we introduce a
separation algorithm for the corresponding scenario subproblems that
exploits projection and KKT conditions, and has some clear advantages over
generalized Benders decomposition.
Joint work with Andrea Lodi, Giacomo Nannicini, Dimitri Thomopulos

24 novembre 2014, 14h, salle C108 : Denis Cornaz (LAMSADE). Identités de Gallai chromatiques.
Slides

Étant donné un graphe G, nous montrons comment, en retirant une arête du line-graph L(G) par triangle de G, on peut obtenir un graphe S(G) dont les stables sont en bijection avec les colorations (du complémentaire) de G.
Incidemment on obtient des nouvelles réductions de stable max à coloration min, et vice-versa.
Grâce à ce graphe auxiliaire, on peut améliorer la relaxation SDP (fonction théta de Lovasz) pour la coloration (en restant polynomial), et l’amélioration n’est pas seulement théorique mais significative en pratique.
Notons que la même approche détériore le relaxation linéaire (nombre chromatique fractionnaire).

(Mardi) 18 novembre 2014, 14h, salle A707 : Klaus Jansen (Kiel, Allemagne). Approximation algorithms for a knapsack and related scheduling problem.
Slides.