Séminaire d'Optimisation Combinatoire

Lundi 20 janvier 2014 à 14h15 en salle A707

Title: On the MAXIMUM MINIMAL VERTEX COVER problem

Abstract: This talk addresses the MAXIMUM MINIMAL VERTEX COVER problem, which is the maximization version of the well studied INDEPENDENT DOMINATING SET problem, known to be NP-hard and highly inapproximable in polynomial time. Tight approximation results for this problem on general graphs are presented, namely, a polynomial time approximation algorithm that guarantees an n^{-1/2} approximation ratio, while showing that unless P is not equal to NP, the problem is inapproximable within ratio n^{eps-(1/2)} for any strictly positive eps. It is also shown that the problem is fixed-parameter tractable with respect to the size of an optimal solution and to the size of a maximum matching. Joint work with Nicolas Boria (IDSIA, Universita della Svizzera Italiana, Lugano) and Federico Della Croce (DAI, Politecnico di Torino)

Lundi 27 janvier 2014 à 14h15 en salle A707

Title: Modeling Two-Dimensional Guillotine Problems via Integer Programming

Abstract: Two dimensional cutting problems are about obtaining a set of small items from one or more large stock pieces. In guillotine cutting problems, small rectangular items are obtained from large rectangular stock through cuts that are parallel to the sides of the stock and cross the stock from one side to the other. Guillotine cuts are performed in stages, where each stage consists of a set of parallel guillotine cuts on the shapes obtained in the previous stage. We do not restrict the number of stages, and propose a way of modeling guillotine cuts in Mixed Integer Linear Programs (MIP), by extending to two dimensions an idea originally proposed by Dyckhoff for the one dimensional case. Despite the relevance of the problem, to the best of our knowledge this is the first attempt to model guillotine restrictions that works in practice. The model we propose has pseudo-polynomial size, however, we discuss conditions under which the number of variables can be safely reduced. We report a set of computational experiments investigating the actual size of the proposed model for a set of benchmark instances, the quality of the solutions which can be obtained by restricting the set of considered variables, and the size of the instances which can be solved by a state-of-the-art MIP solver. Joint work with Fabio Furini and Dimitri Thomopulos.

Lundi 3 février 2014 à 14h15 en salle C516

Title: Exact algorithms for Weak Roman Domination

Abstract: We consider the Weak Roman Domination problem. Considering the Great Roman Empire, the aim is to put "legions" on some cities of the Empire in order to defend all of them in case of a ennemy attack. More formally, the goal is to find a weak roman domination function (wrd-function) of minimum cost, i.e. a function which associates to each vertex either 0, 1 or 2 legions, such that (1) each vertex is defended, that is it has at least one legion in its closed neighborhood (which includes itself), and (2) if one vertex without legion is attacked, a neighboring legion can move onto this vertex to protect it, and still all vertices of the graph are defended. In this talk, I will present two exact algorithms to solve this problem in time better than the trivial enumeration algorithm: I will first present an algorithm in O^*(2^n) time needing exponential space, and then describe an O^*(2.2279^n) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the Red-Blue Dominating Set problem.

Lundi 10 février 2014 à 14h15 en salle A707

Title: The Edge-Recoloring Cost of Paths and Cycles in Edge-Colored Graphs and Digraphs

Abstract: In this talk we introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property \pi, a c-edge-colored graph G^c (resp., digraph D^c) not satisfying \pi, and an edge-recoloring cost matrix R=[r_{ij}]_{c.c} where r_{ij}\geq 0 denotes the cost of changing color i of edge e to color j. Basically, in this kind of problem the idea is to change the colors of one or more edges of G^c (resp., oriented edges in D^c) in order to construct a new c'-edge-colored G^{c'}_{new} with c' \leq c (resp., D^{c'}_{new}) such that the total edge-recoloring cost is minimized and property \pi is satisfied. Here, we are especially concerned with properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs. Some related problems and future directions are also presented.

Lundi 17 février 2014 à 14h15 en salle A707

Title: Strong edge-colouring of graphs and related problems

Abstract: A strong edge-colouring of a graph is a proper edge-colouring such that every colour class induces a matching. Equivalently, it can be seen as a proper vertex-colouring of the square of the line graph. During this talk, after a short overview of structural results, we will focus on the complexity aspects of the problem. We will show that deciding whether a given graph admits a strong edge-colouring with at most k colours (k=4, 5 or 6) is an NP-complete problem even when restricted to several subclasses of planar graphs. In the last part of the talk we will discuss the complexity of another related problem: the maximum induced matching. This is a joint work with Hervé Hocquard and Pascal Ochem.

Lundi 3 mars 2014 à 14h15 en salle A707

Title: Designing a computationally efficient FPTAS for stochastic dynamic programs

Abstract: We propose a computationally efficient Fully Polynomial-Time Approximation Scheme (FPTAS) for convex stochastic dynamic programs using the technique of K-approximation sets and functions introduced by Halman et al. (2008). This work deals with the convex case only, and it has the following contributions: First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance, and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set. If time permits, we will discuss recent extensions to deal with Markov decision processes with random variables with large (exponential) support, and an application to the optimal management of energy storage devices for renewable energy sources.

Lundi 24 mars 2014 à 14h15 en salle A707

Title: An absolute performance guarantee for a scheduling problem with stepwise payo ffs

Abstract: We consider a single machine scheduling problem with unequal release dates and a common stepwise payoff function for the jobs. The goal is to maximize the sum of the jobs payoff s, which are de fined with regard to some common delivery dates. The problem is strongly NP-hard. We propose a polynomial time approximation algorithm with an absolute guarantee. The time complexity of the approximation algorithm is O(K N log(N)), N being the number of jobs and K the number of delivery dates. Joint work with Christophe Gonzales and Safia Kedad-Sidhoum.

Lundi 31 mars 2014 à 15h en salle A707

Title: On the iterated biclique operator

Abstract: A biclique of a graph $G$ is a maximal induced complete bipartite subgraph of $G$. The biclique graph of G, denoted by KB(G), is the intersection graph of the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever \lim_{k \rightarrow \infty}|V(F^{k}(G))|=\infty (\lim_{k \rightarrow \infty}F^{k}(G)=F^{m}(G) for some m, or F^{k}(G)=F^{k+s}(G) for some k and s \geq 2, respectively). Given a graph G, the iterated biclique graph of G, denoted by KB^{k}(G), is the graph obtained by applying the biclique operator k successive times to G. In this paper we study the iterated biclique graph of G. In particular, we classify the different behaviors of KB^{k}(G) when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yields a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situation for the better known clique operator, where it is not even known if the corresponding problem is decidable.

Lundi 7 avril 2014 à 14h15 en salle A707

Titre : La répartition des ressources dans l'approche du portfolio d'algorithmes

Résumé: Nous nous intéressons à la mise en coopération de plusieurs algorithmes résolvant le même problème avec l'approche du portfolio d'algorithmes. Dans celle-ci, la coopération algorithmique consiste à exécuter concurremment les algorithmes selon un partage des ressources qu'on peut changer dans le temps. Une question difficile en contexte parallèle est de déterminer alors la meilleure répartition des ressources. Nous proposons dans ce séminaire une modélisation inspirée de l'apprentissage qui capture la répartition des ressources en un problème NP-complet. Dans le cas général, ce problème est inapproximable. Nous commençons par considérer des cas particulier où nous pouvons formuler des algorithmes d'approximation garantis. Nous montrons ensuite comment en utilisant ces algorithmes d'approximation et d'autres techniques de résolution comme la programmation dynamique, il est possible de formuler des heuristiques rapides et efficaces pour le problème général. Enfin, nous discutons de quelques résultats sur les problèmes SAT et CSP ainsi que de la portée de nos résultats dans le calcul parallèle.

Mardi 8 avril 2014 à 15h en salle B217

Titre : Détection de communautés dans de grands graphes de terrain

Résumé: Après avoir présenté le contexte autour des graphes de terrain (i.e. des graphes construits à partir de données réelles : réseaux sociaux, réseaux de neurones, etc.) et des problématiques de détection de communautés sous-jacentes, je présenterai 2 contributions : 1) la méthode de Louvain générique, un algorithme capable d'optimiser plusieurs fonctions de qualité pour la recherche de partitions dans des graphes, et capable de traiter de très grandes instances ; 2) une preuve montrant l'inexistence de structure communautaire dans des graphes aléatoires.

Lundi 5 mai 2014 à 14h15 en salle C104

Titre : Énumération des dominants minimaux d'un graphe.

Résumé : Un dominant d'un graphe G, est un sous-ensemble D de sommets de G tel que tout sommet à l'extérieur de D, possède au moins un voisin dans D. Un dominant est dit minimal, s'il ne contient aucun autre dominant. Cet exposé sera consacré aux problèmes d'énumérations et plus particulièrement à l'énumération des dominants minimaux d'un graphe, c'est à dire, le problème consistant à lister tous les dominants minimaux d'un graphe donné. Nous parlerons du rôle central qu'occupe ce problème parmi les problèmes d'énumérations, et je présenterai des méthodes récentes permettant de construire des algorithmes d'énumérations efficaces.

Mardi 6 mai 2014 à 14h15 en salle A707

Title: The Parameterized Complexity of Graph Cyclability

Abstract: The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k; is co-W[1]-hard and give an FPT algorithm for planar graphs. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs. This is joint work with Petr Golovach, Spyridon Maniatis, and Dimitrios Thilikos.

Mardi 13 mai 2014 à 16h en salle A301

Title: Polynomial-Time Algorithms for Coalition Structure Generation in Unimodular Games and Pseudo-Polar Games

Abstract: One important issue in multiagent systems is to analyze how groups of agents may adopt cooperative behavior. In this respect, cooperative game theory provides a formal framework to model and analyze key issues such as the coalition structure generation problem (CSG) and the stable payoff allocation problem. However these problems are known to be computationally hard in general and give rise to various algorithmic contributions for some particular cases. In this paper, we show the potential of pseudo-boolean optimization techniques to solve CSG problems for two particular subclasses of games having a non-empty core, namely unimodular games and pseudo-polar games. More precisely, for unimodular games, we present polynomial-time algorithms to solve the CSG problem and to find an imputation in the core. Then we introduce pseudo-polar games and show that they have a non-empty core. For such games, we also propose a polynomial-time algorithm to solve the CSG problem.

Lundi 26 mai 2014 à 14h15 en salle C104

Title: Modeling convex subsets of points.

Abstract: A subset S of a given set of points in a convexity structure is convex if every given point that is in the convex hull of S is itself in S. We are interested in modeling these convexity restrictions when the given set of points is finite. Such restrictions arise, usually in a low-dimensional space (and subject to additional constraints), in many applications, such as in mining, forestry, location, data mining, political districting, and police quadrant design. Modeling convex subset restrictions is well understood for the standard vector space convexity in the one-dimensional case: optimization and separation are well solved (in linear time), and a polyhedral description in the natural variables and a linear-sized ideal extended formulation are known. On the other hand the optimization problem (to find a maximum weight convex subset of given points with weights of arbitrary signs) is NP-hard for the standard convexity in dimensions three and higher, and inapproximable when the dimension is part of the input. In the two-dimensional plane, the optimization problem is solved in polynomial (cubic) time by dynamic programming [Bautista-Santiago et al., 2011] and, by Carathéodory's Theorem, convexity can be enforced by a polynomial (quartic) number of linear inequalities in the natural binary variables. We seek more compact or tighter formulations and faster separation algorithms in the natural variables, and extended formulations, that can be used as part of more complex optimization models involving convex subsets of given points. We also consider these questions in related convexity structures. (This talk will report on past and current work with numerous co-authors.)

Lundi 30 juin 2014 à 14h15 en salle C104

Title: Identifying codes and metric dimension on selected graph classes

Abstract: An identifying code C of a graph is a dominating set where every vertex of the graph is dominated by a distinct subset of C. In other words, it is a set C of vertices that distinguishes all pairs of vertices using their neighborhood within C. A resolving set is a set S of vertices which distinguishes all pairs of vertices by their respective distances to some vertex of S. For these two concepts, the goal is to minimize the number of vertices in a solution. We present some recent results about these two concepts for specific graph classes, especially interval graphs and permutation graphs. This is joint work with George Mertzios, Aline Parreau, Reza Naserasr and Petru Valicov.