Menu Close

Time table of all LIRMM seminars

All LIRMM seminars, sorted by team or theme

May 2022

Mon Tue Wed Thu Fri Sat Sun
Sunday 1 May
Monday 2 May
Tuesday 3 May
Wednesday 4 May
Thursday 5 May
Friday 6 May
Saturday 7 May
Sunday 8 May
Monday 9 May
Tuesday 10 May
Wednesday 11 May
Thursday 12 May
  • 0 h 00 min – 12 h 00 min Robert Ganian, «Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts»
    Robert Ganian, «Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts»
    0 h 00 min – 12 h 00 min

    Decompositional parameters such as treewidth are commonly used to
    obtain fixed-parameter algorithms for NP-hard graph problems. For
    problems that are W[1]-hard parameterized by treewidth, a natural
    alternative would be to use a suitable analogue of treewidth that is
    based on edge cuts instead of vertex separators. While tree-cut width
    has been coined as such an analogue of treewidth for edge cuts, its
    algorithmic applications have often led to disappointing results: out
    of twelve problems where one would hope for fixed-parameter
    tractability parameterized by an edge-cut based analogue to treewidth,
    eight were shown to be W[1]-hard parameterized by tree-cut width.

    Here, we will discuss an edge-cut based analogue to treewidth called
    edge-cut width. Edge-cut width is, intuitively, based on measuring the
    density of cycles passing through a spanning tree of the graph. Its
    benefits include not only a comparatively simple definition, but
    mainly that it has interesting algorithmic properties: it can be
    computed by a fixed-parameter algorithm, and it yields fixed-parameter
    algorithms for all the aforementioned problems where tree-cut width
    failed to do so.

Friday 13 May
Saturday 14 May
Sunday 15 May
Monday 16 May
Tuesday 17 May
Wednesday 18 May
Thursday 19 May
  • 10 h 00 min – 11 h 00 min Maximilian Gorsky, «Matching Theory, Hamiltonicity, and Barnette's Conjecture»
    Maximilian Gorsky, «Matching Theory, Hamiltonicity, and Barnette's Conjecture»
    10 h 00 min – 11 h 00 min

    Barnette’s Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.

    A graph is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette’s Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.

    Joint work with Sebastian Wiederrecht und Raphael Steiner.

  • 11 h 00 min Miklos Molnar, «Hiérarchies de recouvrement minimales sous contraintes de degrés non uniformes correspondant à des capacités»
    Miklos Molnar, «Hiérarchies de recouvrement minimales sous contraintes de degrés non uniformes correspondant à des capacités»
    11 h 00 min – 11 h 00 min

    Le problème de recouvrement de graphes supposant des bornes de degré hétérogènes sur des nœuds est l’objet de cette présentation. Les bornes représentent des capacités momentanées limitées des nœuds. Nous donnons la formulation exacte de la structure couvrante connexe à coût minimum satisfaisant les contraintes qui est une hiérarchie. Le problème est NP-difficile et la solution n’existe pas toujours. Les conditions nécessaires et suffisantes pour l’existence de la hiérarchie couvrante sont alors présentées. Dans certains cas, la solution peut être approchée et un algorithme est aussi proposé.

Friday 20 May
Saturday 21 May
Sunday 22 May
Monday 23 May
Tuesday 24 May
Wednesday 25 May
Thursday 26 May
Friday 27 May
Saturday 28 May
Sunday 29 May
Monday 30 May
Tuesday 31 May

June 2022

Mon Tue Wed Thu Fri Sat Sun
Wednesday 1 June
Thursday 2 June
  • 10 h 00 min – 11 h 00 min Lars Jaffke, «A logic-based algorithmic meta-theorem for mim-width»
    Lars Jaffke, «A logic-based algorithmic meta-theorem for mim-width»
    10 h 00 min – 11 h 00 min

    We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

    Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

    Joint work with Benjamin Bergougnoux and Jan Dreier.

Friday 3 June
Saturday 4 June
Sunday 5 June
Monday 6 June
Tuesday 7 June
Wednesday 8 June
Thursday 9 June
  • 10 h 00 min – 11 h 00 min Daniel Gonçalves, «On comparable box dimension»
    Daniel Gonçalves, «On comparable box dimension»
    10 h 00 min – 11 h 00 min
    E.3.23 Bâtiment 4 LIRMM,

    Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
    of a translation of the other. The comparable box dimension of a graph
    $G$ is the minimum integer $d$ such that $G$ can be represented as a
    touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We
    show that proper minor-closed classes have bounded comparable box
    dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.

    Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

  • 11 h 00 min Jannis Kurtz, «How to Use Machine Learning in Robust Optimization»
    Jannis Kurtz, «How to Use Machine Learning in Robust Optimization»
    11 h 00 min – 11 h 00 min

    Robust optimization is one of the most popular methods to tackle optimization problems under uncertainty. In this approach we assume that all possible outcomes of the uncertain parameters are contained in a given uncertainty set and the task is to find solutions which are worst-case optimal under all these scenarios.

    In the first part of this talk we study optimization problems under uncertainty which contain a two-stage structure and apply the two-stage robust optimization approach with discrete uncertainty. Two-stage robust problems can be solved by so called column-and-constraint algorithms where iteratively new variables and constraints are generated. Unfortunately solving these problems is computationally very demanding, especially if the second-stage variables are integer. In our work we propose a data-driven heuristic to determine a set of starting scenarios that provide strong lower bounds early in the iterative process. We learn the relevance of scenarios by extracting information from training data using a combined similarity measure between robust problem instances and single scenarios. Our experiments show that predicting even a small number of good start scenarios can considerably reduce the computation time.

    In the second part of this talk we consider the problem of constructing uncertainty sets for robust optimization from historic data. We propose to train deep neural networks on historic data to exclude outliers and extract hidden structures in the data which leads to uncertainty sets which have a more complex structure than the ones constructed by previous approaches. We show that the trained neural networks can be integrated into a robust optimization model by formulating the adversarial problem as a convex quadratic mixed-integer program. Our computations show that our uncertainty sets lead to robust solutions that often outperform the comparison methods both with respect to objective value and feasibility.

    Note: this is a zoom seminar, the link will be communicated later.

Friday 10 June
Saturday 11 June
Sunday 12 June
Monday 13 June
Tuesday 14 June
Wednesday 15 June
Thursday 16 June
  • 10 h 00 min – 11 h 00 min Stavros Kolliopoulos, «Precedence-Constrained Covering Problems with Multiplicity Constraints»
    Stavros Kolliopoulos, «Precedence-Constrained Covering Problems with Multiplicity Constraints»
    10 h 00 min – 11 h 00 min
    Bât 4, salle du séminaire (LIRMM - RDC Entrée)

    We study the approximability of covering problems when the set of
    items chosen to satisfy the covering constraints must be a prefix of a
    given partial order. We examine the general case with multiplicity
    constraints, where item $i$ can be chosen up to $d_i$ times. For the
    basic Precedence-Constrained Knapsack problem (PCKP) we answer an open
    question of McCormick et al. and show the existence of approximation
    algorithms with strongly-polynomial bounds.

    PCKP is a special case, with a single covering constraint, of a
    Precedence-Constrained Covering Integer Program (PCCP). For a general
    PCCP where the number of covering constraints is $m \geq 1,$ we show
    that an algorithm of Pritchard and Chakrabarty for Covering Integer
    Programs can be extended to yield an $f$-approximation, where $f$ is
    the maximum number of variables with nonzero coefficients in a
    covering constraint. This is nearly-optimal under standard
    complexity-theoretic assumptions and rather surprisingly matches the
    bound known for the problem without precedence constraints.

    Joint work with Antonis Skarlatos.

Friday 17 June
Saturday 18 June
Sunday 19 June
Monday 20 June
Tuesday 21 June
Wednesday 22 June
Thursday 23 June
Friday 24 June
Saturday 25 June
Sunday 26 June
Monday 27 June
Tuesday 28 June
Wednesday 29 June
Thursday 30 June

July 2022

Mon Tue Wed Thu Fri Sat Sun
Friday 1 July
Saturday 2 July
Sunday 3 July
Monday 4 July
Tuesday 5 July
Wednesday 6 July
Thursday 7 July
Friday 8 July
Saturday 9 July
Sunday 10 July
Monday 11 July
Tuesday 12 July
Wednesday 13 July
Thursday 14 July
Friday 15 July
Saturday 16 July
Sunday 17 July
Monday 18 July
Tuesday 19 July
Wednesday 20 July
Thursday 21 July
Friday 22 July
Saturday 23 July
Sunday 24 July
Monday 25 July
Tuesday 26 July
Wednesday 27 July
Thursday 28 July
Friday 29 July
Saturday 30 July
Sunday 31 July

No events.

August 2022

Mon Tue Wed Thu Fri Sat Sun
Monday 1 August
Tuesday 2 August
Wednesday 3 August
Thursday 4 August
Friday 5 August
Saturday 6 August
Sunday 7 August
Monday 8 August
Tuesday 9 August
Wednesday 10 August
Thursday 11 August
Friday 12 August
Saturday 13 August
Sunday 14 August
Monday 15 August
Tuesday 16 August
Wednesday 17 August
Thursday 18 August
Friday 19 August
Saturday 20 August
Sunday 21 August
Monday 22 August
Tuesday 23 August
Wednesday 24 August
Thursday 25 August
Friday 26 August
Saturday 27 August
Sunday 28 August
Monday 29 August
Tuesday 30 August
Wednesday 31 August

No events.

September 2022

Mon Tue Wed Thu Fri Sat Sun
Thursday 1 September
Friday 2 September
Saturday 3 September
Sunday 4 September
Monday 5 September
Tuesday 6 September
Wednesday 7 September
Thursday 8 September
Friday 9 September
Saturday 10 September
Sunday 11 September
Monday 12 September
Tuesday 13 September
Wednesday 14 September
Thursday 15 September
Friday 16 September
Saturday 17 September
Sunday 18 September
Monday 19 September
Tuesday 20 September
Wednesday 21 September
Thursday 22 September
Friday 23 September
Saturday 24 September
Sunday 25 September
Monday 26 September
Tuesday 27 September
Wednesday 28 September
Thursday 29 September
Friday 30 September

No events.

October 2022

Mon Tue Wed Thu Fri Sat Sun
Saturday 1 October
Sunday 2 October
Monday 3 October
Tuesday 4 October
Wednesday 5 October
Thursday 6 October
Friday 7 October
Saturday 8 October
Sunday 9 October
Monday 10 October
Tuesday 11 October
Wednesday 12 October
Thursday 13 October
Friday 14 October
Saturday 15 October
Sunday 16 October
Monday 17 October
Tuesday 18 October
Wednesday 19 October
Thursday 20 October
Friday 21 October
Saturday 22 October
Sunday 23 October
Monday 24 October
Tuesday 25 October
Wednesday 26 October
Thursday 27 October
Friday 28 October
Saturday 29 October
Sunday 30 October
Monday 31 October

No events.

November 2022

Mon Tue Wed Thu Fri Sat Sun
Tuesday 1 November
Wednesday 2 November
Thursday 3 November
Friday 4 November
Saturday 5 November
Sunday 6 November
Monday 7 November
Tuesday 8 November
Wednesday 9 November
Thursday 10 November
Friday 11 November
Saturday 12 November
Sunday 13 November
Monday 14 November
Tuesday 15 November
Wednesday 16 November
Thursday 17 November
Friday 18 November
Saturday 19 November
Sunday 20 November
Monday 21 November
Tuesday 22 November
Wednesday 23 November
Thursday 24 November
Friday 25 November
Saturday 26 November
Sunday 27 November
Monday 28 November
Tuesday 29 November
Wednesday 30 November

No events.

December 2022

Mon Tue Wed Thu Fri Sat Sun
Thursday 1 December
Friday 2 December
Saturday 3 December
Sunday 4 December
Monday 5 December
Tuesday 6 December
Wednesday 7 December
Thursday 8 December
Friday 9 December
Saturday 10 December
Sunday 11 December
Monday 12 December
Tuesday 13 December
Wednesday 14 December
Thursday 15 December
Friday 16 December
Saturday 17 December
Sunday 18 December
Monday 19 December
Tuesday 20 December
Wednesday 21 December
Thursday 22 December
Friday 23 December
Saturday 24 December
Sunday 25 December
Monday 26 December
Tuesday 27 December
Wednesday 28 December
Thursday 29 December
Friday 30 December
Saturday 31 December

No events.

January 2023

Mon Tue Wed Thu Fri Sat Sun
Sunday 1 January
Monday 2 January
Tuesday 3 January
Wednesday 4 January
Thursday 5 January
Friday 6 January
Saturday 7 January
Sunday 8 January
Monday 9 January
Tuesday 10 January
Wednesday 11 January
Thursday 12 January
Friday 13 January
Saturday 14 January
Sunday 15 January
Monday 16 January
Tuesday 17 January
Wednesday 18 January
Thursday 19 January
Friday 20 January
Saturday 21 January
Sunday 22 January
Monday 23 January
Tuesday 24 January
Wednesday 25 January
Thursday 26 January
Friday 27 January
Saturday 28 January
Sunday 29 January
Monday 30 January
Tuesday 31 January

No events.

February 2023

Mon Tue Wed Thu Fri Sat Sun
Wednesday 1 February
Thursday 2 February
Friday 3 February
Saturday 4 February
Sunday 5 February
Monday 6 February
Tuesday 7 February
Wednesday 8 February
Thursday 9 February
Friday 10 February
Saturday 11 February
Sunday 12 February
Monday 13 February
Tuesday 14 February
Wednesday 15 February
Thursday 16 February
Friday 17 February
Saturday 18 February
Sunday 19 February
Monday 20 February
Tuesday 21 February
Wednesday 22 February
Thursday 23 February
Friday 24 February
Saturday 25 February
Sunday 26 February
Monday 27 February
Tuesday 28 February

No events.

March 2023

Mon Tue Wed Thu Fri Sat Sun
Wednesday 1 March
Thursday 2 March
Friday 3 March
Saturday 4 March
Sunday 5 March
Monday 6 March
Tuesday 7 March
Wednesday 8 March
Thursday 9 March
Friday 10 March
Saturday 11 March
Sunday 12 March
Monday 13 March
Tuesday 14 March
Wednesday 15 March
Thursday 16 March
Friday 17 March
Saturday 18 March
Sunday 19 March
Monday 20 March
Tuesday 21 March
Wednesday 22 March
Thursday 23 March
Friday 24 March
Saturday 25 March
Sunday 26 March
Monday 27 March
Tuesday 28 March
Wednesday 29 March
Thursday 30 March
Friday 31 March

No events.

April 2023

Mon Tue Wed Thu Fri Sat Sun
Saturday 1 April
Sunday 2 April
Monday 3 April
Tuesday 4 April
Wednesday 5 April
Thursday 6 April
Friday 7 April
Saturday 8 April
Sunday 9 April
Monday 10 April
Tuesday 11 April
Wednesday 12 April
Thursday 13 April
Friday 14 April
Saturday 15 April
Sunday 16 April
Monday 17 April
Tuesday 18 April
Wednesday 19 April
Thursday 20 April
Friday 21 April
Saturday 22 April
Sunday 23 April
Monday 24 April
Tuesday 25 April
Wednesday 26 April
Thursday 27 April
Friday 28 April
Saturday 29 April
Sunday 30 April

No events.