# Séminaires 2016 - 2017

**Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.**

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à **14h30** en **Salle C319**. Les responsables sont **Louis Esperet** et **András Sebő**, n'hésitez pas à les contacter.

- Jeudi 4
mai 2017
**(à 14h30)**:**Claire Pennarun**(LaBRI, Bordeaux) : tba

tba

- Jeudi 23 février 2017
**(à 14h30)**:**Cong Bang Huynh**(Institut Fourier, Grenoble) : Une mesure de probabilité sur l'ensemble des chemins auto-évitants infinis

On cherche à définir une mesure de probabilité naturelle sur l'ensemble des chemins auto-évitants infinis (noté SAW_infty) dans le demi-plan H. Cette question a été étudiée par Kesten et Lawler à partir de mesures sur des chemins auto-évitants finis. Notre méthode construit directement une famille à un paramètre de mesures sur SAW_\infty, (P_\lambda)_{\lambda>\lambda_c}. Quand \lambda\to\lambda_c on espère obtenir une limite qui ressemble à la mesure de Kesten et Lawler. Je décrirai quelques propriétés de cette famille de mesures.

- Mardi 21 février 2017
**(à 11h)**:**Seffi Naor**(Technion, Haifa, Israël) : Multi-label classification with pairwise relations

Motivated by various applications in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics, we introduce the metric multi-labeling problem. The input is a set of objects with pairwise relations, given as a weighted graph over the objects, together with a label set and assignment costs of labels to objects. Departing from classical work on the metric labeling problem, assignment costs may be either positive or negative, reflecting a recommendation given by a local learning process which infers label preferences of objects. However, the learning process ignores pairwise relations of objects. Clearly, the labeling cost for completely agreeing with this recommendation is the minimum possible, and this is our benchmark labeling. The objective is to find an assignment of (multiple) labels to objects, at least one for each object, minimizing the sum of the following two terms: (1) the deviation cost from the benchmark labeling, and (2) the separation cost between pairs of similar objects receiving different label sets. Thus, the goal is to globally optimize the assignment of label sets to objects, while taking into account local preferences of objects. We obtain a (tight) 2-approximation for this problem.

Additionally, in many natural applications a bound is given on the number of labels that can be assigned to an object. This leads to a very interesting problem of simultaneous rounding of many (fractional) points contained in a uniform matroid polytope, while bounding pairwise distances. We achieve a true O(log k)-approximation for this problem (k is the number of labels).

Joint work with Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, and Roy Schwartz.

- Jeudi 2 février 2017
**(à 14h30)**:**Ararat Harutyunyan**(Université de Toulouse) : List Coloring Digraphs

The dichromatic number of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs. In this talk, we will focus on the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We show that the list dichromatic number of a digraph can be arbitrarily larger than its dichromatic number, a property that is well-known for graphs. Moreover, we show that other results known on graphs describing the relationship between the chromatic and list chromatic numbers generalize naturally in the setting of digraphs.

Based on joint work with Julien Bensmail (Nice, Sophia-Antipolis) and Khang Le (ENS de Lyon).

- Jeudi 12 janvier 2017
**(à 14h30)**:**Marthe Bonamy**(LaBRI, Bordeaux) : Reed's conjecture and strong edge coloring

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex "sees few edges" in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.

This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

- Jeudi 8 décembre 2016
**(à 14h30)**:**Eric Fusy**(LIX, Palaiseau) : Bijections pour cartes planaires à bords

Nous présentons une méthode bijective générale pour les cartes planaires, basée sur certaines orientations. Cette méthode peut être adaptée pour les cartes planaires à bords et nous montrerons en particulier comment elle s'applique aux triangulations à bords et comment contrôler le paramètre de maille (triangulations à bords sans boucle, ou sans boucle ni arête multiple)

- Vendredi 2 Décembre 2016
**(à 10h)**:**András Gyárfás**(Renyi Institute, Budapest) : Results and problems on chi-bounded graph classes

tba

- Jeudi 1er Décembre 2016
**(à 10h)**:**Dieter Rautenbach**(Université d'Ulm, Allemagne) : Zero forcing

A set Z of vertices of a graph G is a zero forcing set of G if initially labeling all vertices in Z with 1 and all remaining vertices of G with 0, and then, iteratively and as long as possible, changing the label of some vertex u from 0 to 1 if u is the only neighbor with label 0 of some vertex with label 1, results in the entire vertex set of G. The zero forcing number Z(G), defined as the minimum order of a zero forcing set of G, was proposed as an upper bound of the corank of matrices associated with G, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. We discuss such bounds and some of the corresponding extremal graphs.

Joint work with M. Gentner, L.D. Penso, and U.S. Souza.

- Mardi 29 Novembre 2016
**(à 14h30)**:**Vincent Cohen-Addad**(ENS, Paris) : The power of local search for clustering

What are the performance guarantees of the algorithms used in practice for clustering problems? In a paper with Phil Klein and Claire Mathieu, we give the first polynomial-time approximation schemes for the following problems:

(1) uniform facility location in edge-weighted planar graphs;

(2) k-median and k-means in edge-weighted planar graphs;

(3) k-means in Euclidean space of bounded dimension.

The algorithm is a standard, widely-used local search heuristic where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/\eps^{O(1)} centers. In a second line of work with Chris Schwiegelshohn, we show that this algorithm also performs near-optimaly for several types of instances that aim at characterizing the structure of real-world instances stemming from machine learning and data analysis. Those results make a step toward understanding the success of local search heuristics in practice.

- Jeudi 10 novembre 2016
**(à 14h30)**:**Hojin Choi**(KAIST, Daejeon, Corée du Sud) : Online Ramsey theory for the cycle of length 3

Online Ramsey theory is a study on the online version of Ramsey theory, based on online Ramsey game. Given a fixed graph H and a class C of graphs, an online Ramsey game for H on C} is a game between two players Builder and Painter with the following rules: On each round, Builder draws a new edge with the constraint that the resulting graph must be in C, and Painter colors the new edge either red or blue.

Builder wins if Builder can force Painter to make a monochromatic copy of H at some point of the game, and Painter wins if a monochromatic copy of H can be avoided forever. Online Ramsey game was first investigated in 2004 by Grytczuk, Haluszczak, and Kierstead where they studied online Ramsey game on forests, k-colorable graphs, outerplanar graphs, and planar graphs. Recently, Petrickova continued the study on planar graphs further by disproving a conjecture by Grytczuk, Haluszczak, and Kierstead.

We focus on characterizing a graph F such that Painter wins the online Ramsey game for C_3 on F-free graphs, while a graph is F-free if the graph does not contain F as a subgraph; we succeed the characterization except for when F is one particular graph. We also prove that Painter wins the online Ramsey game for C_3 on K_4-minor-free graphs; this extends a result by Grytczuk, Haluszczak, and Kierstead.

This is joint work with Ilkyoo Choi, Jisu Jeong, and Sang-il Oum.

- Jeudi 3 novembre 2016
**(à 14h30)**:**Quentin Fortier**(G-SCOP) : Packing with matroid constraints

A theorem of Edmonds ensures that k-arc-connectivity in a rooted directed graph is equivalent to the existence of a packing of k spanning rooted arborescences. Frank conjectured a generalization of this theorem where the packing must verify an additional constraint, given by a matroid. We prove this conjecture for particular cases and provide a counterexample for the general case.

Joint work with Zoltán Szigeti, Csaba Király and Shin-ichi Tanigawa.

- Mardi 18 octobre 2016
**(à 10h15)**:**Imre Barany**(Renyi Institute, Budapest) : Curves in R^d intersecting every hyperplane at most d+1 times

A partial result: if a planar curve intersects every line in at most 3 points, then it can be partitioned into 4 convex curves. This result can be extended to R^d: if a curve in R^d intersects every hyperplane at most d+1 times, then it can be split into M(d) convex curves. The extension implies a good, asymptotically precise, lower bound on a geometric Ramsey number.

Joint result with the late Jiri Matousek and Attila Por.

- Jeudi 22 septembre 2016
**(à 14h30)**:**Marthe Bonamy**(LaBRI, Bordeaux) : Tight lower bounds for the complexity of multicoloring

In the multicoloring problem, also known as (a:b) or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph with parameters a and b. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science. We study the complexity of determining whether a graph has an (a:b)-coloring. Nederlof showed in 2008 a (b+1)^n*n^O(1)-time algorithm for (a:b)-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time 2^o(log b)*n unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we also prove that the existing algorithms for the r-monomial detection problem are optimal under ETH.

This is joint work with Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala and Marcin Wrochna (University of Warsaw).

- Mardi 13 septembre 2016
**(à 14h30)**:**Sylvia Boyd**(Université d'Ottawa) : Experimenting with a New Set of Trees for the Best-of-Many Christofides Algorithm for the Metric Travelling Salesman Problem

The well-known Christofides algorithm for the metric Travelling Salesman Problem (TSP) gives a 3/2-approximation for the problem, and involves finding a minimum cost spanning tree T of the graph, and then a minimum cost perfect matching of the odd degree nodes of T. In the best-of-many variation of this problem, one begins with a collection of spanning trees rather than just one, finds the minimum cost perfect matching for the odd degree nodes for each of these trees, and then keeps the best final TSP result. Recently Genova and Williamson showed empirically that this method performs significantly better than the Christofides method.

We explore the best-of-many Christofides idea for a different set of spanning trees. This set of trees is exponential in size, however it has the advantage that without generating the trees explicitly we can find the best TSP solution for the whole set with just one application of a minimum cost perfect matching algorithm.

Joint work with Nicholas Desjardin.

- Jeudi 8 septembre 2016
**(à 14h)**:**Alantha Newman**(G-SCOP) : The Alternating Stock Size Problem and the Gasoline Puzzle

Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms.

We consider a related problem, which we call the alternating stock size problem, where the number of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79.

Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovasz, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.

Joint work with Heiko Roeglin (Universitaet Bonn) and Johanna Seif (ENS Lyon).

- Jeudi 8 septembre 2016
**(à 11h)**:**Michael Tarsi**(Tel-Aviv University) : The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem

We design an arsenal of methods for constructing graphs, in particular Snarks, with circular flow number at least 5. As one indication to the diversity and density of the obtained family of graphs. we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete. At the core of our constructions is the Algebra of symmetric unions of integer open intervals in the ring R/5Z and its Graphic Sub-algebra. Introducing and studying these Algebras is a part of the talk.

Joint work with Louis Esperet and Giuseppe Mazzuoccolo.