Séminaires 2016 - 2017
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.
|3 novembre 2016||Quentin Fortier
|Packing with matroid constraints|
|18 octobre 2016||Imre Bárány
(Rényi Institute, Budapest)
|Curves in R^d intersecting every hyperplane at most d+1 times|
|22 septembre 2016||Marthe Bonamy
|Tight lower bounds for the complexity of multicoloring|
|13 septembre 2016||Sylvia Boyd
|Experimenting with a New Set of Trees for the Best-of-Many Christofides Algorithm for the Metric Travelling Salesman Problem|
|8 septembre 2016||Alantha Newman
|The Alternating Stock Size Problem and the Gasoline Puzzle|
|8 septembre 2016||Michael Tarsi
|The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem|
- 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.