Nos tutelles

CNRS Dauphine PSL *



Séminaires du Pôle 2 : "Optimisation combinatoire, algorithmique"

publié le , mis à jour le


Fabio Furini et Florian Sikora

Liste de diffusion.

Possibilité de s’inscrire à la liste de diffusion en envoyant un email à :
florian . sikora @ dauphine . fr

Les séminaires ont lieu en général le lundi à 14h.

Prochains séminaires :

lundi 11 décembre 2017, 14h, A 304 : Ararat Harutyunyan (LAMSADE) : A disproof of the normal graphs conjecture

Abstract : A graph G is called normal if there exist two coverings, C and S, of its vertex set such that every member of C induces a clique in G, every member of S induces an independent set in G, and any clique in C and independent set in S have a non-empty intersection. Normal graphs derive their motivation from information theory, where they are related to the Shannon capacity of a graph. In particular, they form a family which extends the class of perfect graphs. It was conjectured by De Simone and Körner [DAM ’99] that a graph G is normal if G does not contain C_5, C_7 and the complement of C_7 as an induced subgraph. Using random graphs and rather routine probabilistic methods, we give a disproof of this conjecture.

Joint work with Lucas Pastor (G-SCOP, Grenoble) and Stéphan Thomassé (ENS Lyon).

date à préciser : Benoît Gaüzère (LITIS) : Graph edit distance as a quadratic assignment problem

(séminaire commun avec le pôle 3)

Graphs allow to encode structural information included within
data used in chemical or pattern recognition problems. However,
conversely to vectors defined in an euclidean space, the
definition of a graph (dis)similarity measure is not
straightforward, but required to compute prediction models. One
of the most well known dissimilarity measure is the graph edit
distance. Despite its good interpretability, the computation of a
graph edit distance between two graphs is an NP-Hard
problem. Therefore, its application remains limited to small
graphs. During this presentation, I will introduce a formal
definition of this metric between graphs as a quadratic
assignment problem and some methods used in pattern recognition
to approximate an optimal solution. Considering approximations
allows us to apply this framework to chemoinformatics problems.

Séminaires précédents :

lundi 20 novembre 2017, 14h, P 301 : Julien Baste (LIP6) : F-M-DELETION parameterized by treewidth

For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a set S of vertices of G of size at most k such that G without the vertices of S does not contain any of the graphs of F as a minor. This problem is a generalization of some well known problems as VERTEX COVER (F=K_2), FEEDBACK VERTEX SET (F=K_3), or VERTEX PLANARIZATION (F=K_5, K_3,3 ). We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of the input graph, denoted by tw. Our objective is to determine, for a fixed F, the smallest function f such that F-M-DELETION can be solved in time f(tw)*poly(n) on n-vertex graphs.

lundi 13 novembre 2017, 14h, salle A (C206, 2ème étage) : Tomáš Toufar (Charles University, Czech Republic) : Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices


We study the Steiner Tree problem, in which a set of terminal vertices
needs to be connected in the cheapest possible way in an edge-weighted
graph. This problem has been extensively studied from the viewpoint of
approximation and also parametrization. In particular, on one hand
Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if
parameterized by the number of non-terminals (Steiner vertices) in the
optimum solution. In contrast to this we
give an efficient parameterized approximation scheme (EPAS), which
circumvents both hardness results. Moreover, our methods imply the
existence of a polynomial size approximate kernelization scheme
(PSAKS) for the assumed parameter.
We further study the parameterized approximability of other variants
of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For
neither of these an EPAS is likely to exist for the studied parameter :
for Steiner Forest an easy observation shows that the problem is
APX-hard, even if the input graph contains no Steiner vertices. For
Directed Steiner Tree we prove that computing a constant approximation
for this parameter is W[1]-hard. Nevertheless, we
show that an EPAS exists for Unweighted Directed Steiner Tree. Also we
prove that there is an EPAS and a PSAKS for Steiner Forest if in
addition to the number of Steiner vertices, the number of connected
components of an optimal solution is considered to be a parameter.

lundi 16 octobre 2017, 14h, salle A (2ème étage) : Eunjung Kim (LAMSADE) : Erdos-Posa Property of Chordless Cycles and its Applications

A chordless cycle is a cycle of length at least 4 that has no chord. We prove that the class of all chordless cycles has the Erdos-Posa property, which resolves the major open question concerning the Erdos-Posa property. We complement our main result by showing that the class of all chordless cycles of length at least l for any fixed l ≥ 5 does not have the Erdos-Posa property.

Our proof for chordless cycles is constructive : in polynomial time, one can either find k + 1 vertex-disjoint chordless cycles, or ck2 log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O(opt log opt) for Chordal Vertex Deletion, which improves the best known approximation by Agrawal et. al. The improved approximation algorithm entails improvement over the known kernelization for Chordal Vertex Deletion.

As a corollary, for a non-negative integral function w defined on the vertex set of a graph G, the minimum value \sum_x\in S w(x) over all vertex sets S where G − S is forest is at most O(k2 log k) where k is the maximum number of cycles (not necessarily vertex-disjoint) in G such that each vertex v is used at most w(v) times.

lundi 2 octobre 2017, 14h, P303 : Giuseppe F. Italiano (Universita’ di Roma "Tor Vergata") : 2-Connectivity in Directed Graphs

We survey some recent results on 2-edge and 2-vertex
connectivity in directed graphs. Despite being complete analogs of the
corresponding notions on undirected graphs, in digraphs 2-connectivity
has a much richer and more complicated structure. For undirected
graphs it has been known for over 40 years how to compute all bridges,
articulation points, 2-edge- and 2-vertex-connected components in
linear time, by simply using depth first search. In the case of
digraphs, however, the very same problems have been much more
challenging and have been tackled only very recently.

Exposés de 2016-2017.
Exposés de 2015-2016.
Exposés de 2014-2015.

Pour les exposés antérieurs, voir cette page.



  • Lundi 27 mars 2017 14:00-16:00 - Valia Mitsou

    On the complexity of defective coloring

    Notes de dernières minutes : B203 : (LIRIS, Lyon1) :

  • Lundi 3 avril 2017 14:00-15:00 - Valentin Garnero - (INRIA COATI)

    Seminaire de Valentin Garnero : On augmenting matchings via bounded-length augmentations

    Lieu : P 301

  • Jeudi 20 avril 2017 13:30-14:30 - Aurélie Lagoutte - G-SCOP

    Séminaire d’Aurélie Lagoutte

    Lieu : C110

  • Vendredi 28 avril 2017 14:15-15:30 - Edouard Bonnet

    Séminaire d’Edouard Bonnet

    Lieu : D120

  • Jeudi 11 mai 2017 14:00-15:00 - Giorgio Lucarelli - Grenoble

    Séminaire pole 2 de Giorgio Lucarelli

  • Lundi 12 juin 2017 14:00-15:00 - Emily Speakman

    Séminaire pole 2 Emily Speakman

    Résumé : Title : Quantifying Double McCormick : Some Geometric Insight for Global Optimization Algorithms
    When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the bounds defining the box. In this manner, we precisely quantify the strength of the different possible relaxations defined by all three groupings, in addition to the trilinear hull itself. As a by product, we characterize the best double McCormick relaxation.

  • Lundi 26 juin 2017 14:00-15:00 - Stéphane Canu - LITIS - INSA de Rouen

    Séminaire de Stéphane Canu - Variable selection and outlier detection as a MIP

    Résumé : Title : Variable selection and outlier detection as a MIP
    Abstract : Dimension reduction or feature selection is an effective strategy to handle contaminated data and to deal with high dimensionality while providing better prediction. To deal with outlier proneness and spurious variables, we propose a method performing the outright rejection of discordant observations together with the selection of relevant variables. To solve this problem, it is recasted as a mixed integer program which allows the use of efficient commercial solver. Also we propose an alternate projected gradient algorithm (proximal) so get a nice appoximated solution.

    Lieu : A304

    Notes de dernières minutes : Séminaire commun Pole 2 / Pole 3

  • Lundi 3 juillet 2017 14:00-15:00 - Roland Grappe - LIPN

    Séminaire pole 2 : Roland Grappe

    Lieu : D 102

  • Lundi 10 juillet 2017 14:00-15:00 - Jon Lee

    Séminaire pole 2 : Jon Lee

  • 1 | 2

Ajouter un événement iCal