Séminaire d'Optimisation Combinatoire

Lundi 13 février 2012 à 14h salle A711

Titre : Approximation différentielle des problèmes d'optimisation SNP

Abstract: We revisit the class SNPO of the SNP optimization problems under the differential approximation paradigm, focusing on three questions: what is the largest k such that the k-ary boolean Constraint Satisfaction Problems, CSP are DAPX? more generally, how affine and differential approximation preserving reductions do arrange SNPO problems? in a more structural point of view, what differential approximation guarantee can we expect from local optima? We here show that 3-ary boolean CSP are 0,2146-differential approximable. We also show that any (2k)-ary boolean CSP is equivalent to MaxNAE(2k)Sat, and that any (2k+1)-ary CSP is (r/2)-differential approximable, if MaxNAE(2k)Sat is r-differential approximable. We finally review some interesting observations regarding neighborhood structures, notably: on the one hand, 1-bounded local optima are 1/(n+1)-differential approximate for MaxNAE2Sat; on the other hand, given any solution of any k-ary boolean CSP, its k-bounded neighborhood contains a solution that is (1/n^k)-differential approximate. We therefore leave many questions unanswered, in particular: are 4-ary boolean CSP constantly differential approximable? what about (2k)-ary boolean CSP vs. (2k-1)-ary boolean CSP? However, this talk also aims at providing somme clues in order to go further. The talk is based on a joint work with Jean-François Culus and Frédéric Roupin

Lundi 12 mars 2012 à 14h salle B207

Title: Domination-like problems parameterized by tree-width

Abstract: Parameterized complexity allows one to study more precisely the theoretical complexity of computational problems, by considering one or more problem-specific parameters which may be small compared to the whole size of the input. During this talk, we will present some new results on the parameterized complexity of a generalization of domination-like problems when parameterized by the tree-width of the input graph. The best known FPT algorithm only deals with finite or cofinite sets Sigma and rho; we will give an algorithm which extends this result to ultimately periodic sets Sigma and Rho. On the other hand, we will prove that for some (infinitely many) cases of sets Sigma and Rho, the problem [Sigma,Rho]-Domination becomes W[1]-hard when parameterized by tree-width. This latter result is of particular interest, as very few problems are known not to be FPT when parameterized by tree-width.

Mardi 20 mars 2012 à 11h salle B207

Title: Domination when the stars are out

Abstract: Recently, Chudnovsky and Seymour proved a structural characterization of claw-free graphs, in a series of 7 papers over 250 pages. Whereas their proof is existential, we algorithmize the characterization for claw-free graphs by Chudnovsky and Seymour and give an efficient algorithm for decomposing claw-free graphs. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are not fixed-parameter tractable on the slightly larger class of graphs that exclude K_{1,4} as an induced subgraph. Our results provide a dichotomy for K_{1,L}-free graphs and show that the problems are fixed-parameter tractable if and only if L = 3. The algorithms we obtain generalize and unify several earlier algorithms for problems on claw-free graphs, and turn the existential decomposition by Chudnovsky and Seymour into an efficient constructive decomposition.(Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger.)

Lundi 26 mars 2012 à 14h salle A707

Title: Parameterized complexity, kernelization algorithms and Conflict Packing

Abstract: Parameterized complexity is a theoretical framework measuring the difficulty of decision problems according to the size of the instance and some parameter k related to the problem. A parameterized problem is said to be FPT whenever it can be solved in f(k).poly(n) time, where f() is any computable function. Equivalently, a problem P is FPT iff it admits a kernelization algorithm, i.e. a polynomial time algorithm that given an instance (I,k) of P outputs an equivalent instance (I',k') of P such that |I'| <= g(k) and k' <= k. In this talk, I will present a (simple) parameterized algorithm as well as several kernelization algorithms for the Vertex Cover problem. Next, I will present the Conflict Packing technique, introduced in a joint work with Christophe Paul and Stéphan Thomassé and allowing to obtain polynomial kernels for several modification problems. I will describe in particular how this technique can be applied to the Feedback Arc Set in Tournaments problem, obtaining a kernel with at most 4k vertices. To conclude, I will explain how the ideas used on FAST can be applied to several other problems.

Mardi 27 mars 2012 à 14h salle A711

Titre : Algorithmes paramétrés pour le consensus d'arbres phylogénétiques

Abstract: Dans cet exposé, on considère divers problèmes de consensus entre arbres étiquetés aux feuilles. Etant donnée une collection d'arbres étiquetés T1,...,Tk, le problème du superarbre d'accord consiste à rechercher un arbre étiqueté T qui contienne chaque Ti comme sous-arbre. On décrira dans un premier temps des algorithmes polynomiaux résolvant le problème du superarbre d'accord dans le cas d'arbres enracinés. On étudiera ensuite deux relaxations du problème qui permettent de prendre en compte les désaccords entre arbres sources. La première relaxation, appelée Maximum Rooted Triplet Consistency, s'applique au cas où les arbres sources sont des triplets enracinés, c'est-à-dire des arbres enracinés à trois feuilles. Elle consiste à rechercher un plus grand sous-ensemble des triplets qui admette un superarbre d'accord. La seconde relaxation, appelée Maximum Agreement Supertree, s'applique au cas d'arbres sources quelconques. Elle consiste à rechercher un plus grand sous-ensemble des étiquettes pour lesquelles on peut construire un superarbre d'accord. Bien que ces deux relaxations soient NP-difficiles, on verra qu'elles admettent des algorithmes paramétrés efficaces, dûs à [Guillemot, Mnich, 2010] et [Fernandez-Baca, Guillemot, Shutters, Vakati 2012].

Mercredi 28 mars 2012 à 14h salle A707

Titre : Méthodes pour l'énumération

Résumé : Je vais présenter dans cet exposé des problèmes d'énumérations, c'est à dire qu'on veut lister toutes les solutions d'un problème. Le but est de réaliser cette tâche avec un algorithme de complexité la plus faible possible. Dans ce cadre on s'intéresse à la fois au temps total de l'algorithme et au délai entre deux solutions. Je vais présenter quatres méthodes pour attaquer des problèmes d'énumérations. Ces méthodes ont leur intérêt propre et peuvent (et on été) utilisées pour des problèmes classique de décision ou d'optimisation. Il s'agit de : - représentation de problèmes par des formules (techniques combinatoires et logiques) - représentation de problèmes par des polynômes (algorithmes probabilistes) - décomposition de graphes, matroïdes, hypergraphes (algorithmes à complexité paramétré) - approximation à l'aide de polytopes (marche aléatoire)

Lundi 30 avril 2012 à 14h salle C516

Title: Parameterized Proof Complexity

Abstract: The origins of Proof Complexity lie in the program of Cook and Reckow, who aimed to separate P and NP (actually, coNP and NP) by proving that no propositional proof system is polynomially bounded. Having failed to obtain such a general result, students of Proof Complexity have instead focused on proving that stronger and stronger proof systems are not polynomially bounded. Such lower bounds are known for systems such as Resolution and Bounded-depth Frege. We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional CNF formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[2] by showing that there is no fpt-bounded proof system, i.e., that there is no proof system that admits proofs of size f(k).n^{O(1)} where f is a computable function and n represents the size of the propositional formula. We survey results in the area, taking in the parameterized versions of tree-Resolution, Resolution and bounded-depth Frege.

Lundi 11 juin 2012 à 14h salle A307

Title: Separation of Series Constraints for One-Machine Scheduling with Precedence

Abstract: A 1991 paper by Queyranne and Wang proposed three classes of valid constraints for the convex hull of feasible completion times for schedules on a single machine subject to precedence constraints. These classes are called the parallel constraints, serial constraints, and Z constraints. These constraints have been very useful in many contexts. Queyranne and Wang showed how to separate the parallel constraints, but the complexity of separating the serial and Z constraints has remained open. Here we show that it is NP Hard to separate even a very special subclass of serial constraints. We also develop a fast, parametric way to find an earliest feasible deadline for a subset of jobs, and use it to show that separation is polynomial when the precedence constraints are series-parallel. We also note that there is a compact extended formulation of the problem by Wolsey, and in this context separation of both series and parallel constraints becomes trivial. It is surprising that an NP Hard separation problem can "hide" within an extended formulation where separation is much easier. We further consider the case of two-dimensional precedence constraints, whose underlying problem is solvable in polynomial time. We show how to separate the serial constraints in this case as well. Joint work with A. Ridha Mahjoub, and Y. Kobayashi.

Jeudi 21 juin 2012 à 13h salle A301

Title: Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem

Abstract: The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into s stacks of size h that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem. In this work, we show that the PDTC problem can be solved in polynomial time when the number s of stacks is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when h > 5 is a fixed constant, but s is unbounded. This is a joint work with Gianpaolo Oriolo (Università di Roma "Tor Vergata", Italia) and Sara Mattia (IASI-CNR, Italia).

Lundi 2 juillet 2012 à 14h salle A707

Title: Boundary properties of the satisfiability problems

Abstract: The satisfiability problem is known to be NP-complete in general and for many restricted instances, such as formulas with at most 3 variables per clause and at most 3 occurrences per variable, or planar formulas. The latter example refers to graphs representing satisfiability instances. These are bipartite graphs with vertices representing clauses and variables, and edges connecting variables to the clauses containing them. Finding the strongest possible restrictions under which a problem remains NP-complete is important for at least two reasons. First, this can make it easier to establish the NP-completeness of new problems by allowing easier transformations. Second, this can help clarify the boundary between tractable and intractable instances of the problem. In this talk, we address the second issue and reveal the first boundary property of graphs representing satisfiability instances.

Lundi 8 octobre 2012 à 14h en salle A707

Titre : Recherche de motifs dans des graphes colorés

Résumé: Décider si un motif existe dans un graphe coloré sur les sommets est une tâche importante pour certaines applications en biologie. Une grande partie de la littérature est dédiée à la recherche de motifs dans ces graphes lorsqu'une topologie est donnée sur le motif (chemin, arbre, graphe...). Plus récemment, Lacroix et al. ont établi un nouveau problème où le motif n'a pas de topologie mais est simplement un (multi) ensemble de couleurs. On cherche alors un sous-graphe connexe contenant cet ensemble de couleurs. On présentera lors de cet exposé des résultats sur la complexité de ce problème, essentiellement sous l'angle de la complexité paramétrée.

Lundi 12 novembre 2012 à 14h15 en salle A711

Title: Logit Dynamics for Strategic Games: Mixing time and Metastability

Abstract: Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain over the set of strategy profiles of the game whose unique stationary distribution is the long-term equilibrium concept for the game. In [Auletta+, SPAA, 2011], bounds on the rate of convergence of the logit dynamics to this equilibrium are given. However, there are games for which the convergence time is large (e.g. exponential in the number of players) and thus the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than convergence time the chain is quasi-stationary, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called metastability. In this talk, a quantitative definition of metastable probability distributions for a Markov chain is given and the metastability of the logit dynamics is analyzed for some classes of games.

Lundi 26 novembre 2012 à 14h15 en salle B117

Title: The Blue-Red Matching problem: approximations, exact solutions, and applications

Abstract: We will discuss earlier as well as some recent results for the Blue-Red Matching problem: given a graph with red and blue edges, and a bound W, find a maximum matching consisting of at most W edges of each color. We will first prove that Blue-Red Matching is at least as hard as the well-known Exact Matching problem (Papadimitriou and Yannakakis, 1982), for which it is still open whether it can be solved in polynomial time. Next we will present two fast approximation algorithms for Blue-Red Matching as well as a randomized (RNC) one that solves it exactly whp. We will finally show the applicability of our results to the problem of routing and assigning wavelengths to a maximum number of requests in all-optical rings and discuss open questions and ideas for further research. (Based on joint work with Christos Nomikos and Stathis Zachos)

Mercredi 5 decembre 2012 à 14h15 en salle A707

Title: Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Abstract: Existence of an equilibrium in various economic models can be shown to exist by following a certain combinatorially defined path, for example of edges of a labeled polytope similar to the simplex algorithm for linear programming. In addition, such a path has a direction that defines the "index" of an equilibrium. Examples include Sperner's lemma about completely labeled simplices and Nash equilibria in games. We present a general model of "pivoting systems" that shows the essence of the path-following and the directedness argument. We also present a connection of bimatrix games where the paths are exponentially long with signed perfect matchings in Euler graphs, and an algorithm that gives a polynomial-time "shortcut" for these paths. We also present a concept of orientation for the "Euler complexes" or "oiks" introduced by Edmonds, which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colorful pictures and examples wherever possible. (Joint work with Marta Maria Casetti, Julian Merschen and Laszlo Vegh.)

Mardi 11 decembre 2012 à 14h15 en salle A307

Title: Query Complexity and Mathematician's Mastermind

Abstract: After a short introduction into query complexities, we survey old and new results for a Mathematician's version of the classic 2-player board game Mastermind. For the game with n positions and k=n colors, we show that the Codebreaker has a winning strategy that uses only O(n loglog n) guesses for identifying the secret code. This improves the previously best known bounds of Chvatal (Combinatorica, 1983), Goodrich (Information Processing Letters, 2009), and others, which are all of order n log n. We also present a new variant of the Mastermind game - the Hidden Permutation problem. We present matching upper and lower bounds for this problem, both for deterministic and randomized query schemes. The deterministic query complexity is Theta(n log n), which, surprisingly, improves to Theta(n log log n) in the randomized setting. The result on Mastermind is joint work with Benjamin Doerr (Max Planck Institute for Informatics), Reto Spoehel (MPI Informatics), and Henning Thomas (ETH Zuerich), and is to appear at SODA 2013. The result on the Hidden Permutation problem is joint work with Peyman Afshani (MADALGO Aarhus), Manindra Agrawal (IIT Kanpur), Benjamin Doerr, Kasper Green Larsen (MADALGO Aarhus), and Kurt Mehlhorn (MPI Informatics).