Time table of all LIRMM seminars

Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. We show how to construct a certain “sparsifer”: a subset of elements, of size $O(|S^{opt}| \cdot 1/\varepsilon)$, where $S^{opt}$ denotes the optimal solution, that is guaranteed to contain a $3/2 + \varepsilon$ approximation, while guaranteeing certain robustness properties. We call such a small subset a //Density Constrained Subset// (DCS), which is inspired by the //Edge-Degree Constrained Subgraph// (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the //density-based decomposition//. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.

We propose highly efficient heuristic and exact algorithms to solve the Electric Autonomous Dial-A-Ride Problem (E-ADARP), which consists in designing a set of minimum-cost routes that accommodate all customer requests for a fleet of Electric Autonomous Vehicles (EAVs). The E-ADARP has two important features: (i) the employment of EAVs and a partial recharging policy; (ii) the weighted-sum objective function that minimizes the total travel time and the total excess user ride time. We first propose a Deterministic Annealing (DA) algorithm to solve the E-ADARP. Partial recharging (i) is handled by an exact route evaluation scheme of linear time complexity. To tackle (ii), we propose a new method that allows effective computations of minimum excess user ride time by introducing a fragment-based representation of paths. To validate the performance of the DA algorithm, we compare our algorithm results to the best-reported Branch-and-Cut (B&C) algorithm results on existing instances. Our DA algorithm provides 25 new best solutions and 45 equal solutions for 84 existing instances. To test the algorithm’s performance on larger-sized instances, we establish new instances with up to 8 vehicles and 96 requests, and we provide 19 new solutions for these instances. Then, we present a highly efficient CG algorithm, which is integrated into the Branch-and-price (B&P) scheme to solve the E-ADARP exactly. Our CG algorithm relies on an effective labeling algorithm to generate columns with negative reduced costs. In the extension of labels, the key challenge is determining all excess-user-ride-time optimal schedules to ensure finding the minimum-negative-reduced-cost route. To handle this issue, we apply the fragment-based representation and propose a novel approach to abstract fragments to arcs while ensuring excess-user-ride-time optimality. We then construct a new graph that preserves all feasible routes of the original graph by enumerating all feasible fragments, abstracting them to arcs, and connecting them with each other, depots, and recharging stations in a feasible way. On the new graph, we apply strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. In the computational experiments, we solve 71 out of 84 instances optimally, improve 30 previously reported lower bounds, and generate 41 new best solutions on previously solved and unsolved instances.

Au cours de cette présentation, je présenterai les travaux en cours sur l’élaboration d’une méthodologie généralisable pour développer des systèmes radiologiques intelligents et fiables. Notre méthodologie, appelée trustworthy-AI-by-design, vise à comprendre comment développer des systèmes d’IA pour la radiologie qui répondent aux futures exigences européennes en matière d’IA digne de confiance. Je présenterai le déploiement et les tests de la méthodologie trustworthy-AI-by-design sur deux cas d’utilisation distincts : 1) la détection de la maladie COVID-19 sur des tomographies thoraciques en utilisant de l’apprentissage profond et 2) un système d’alerte et de prédiction de non-présentation des patients à leur rendez-vous radiologique qui s’appuie sur des modèles d’apprentissage automatique. Nos premières analyses montrent que les différents critères éthiques d’une IA digne de confiance nécessitent des méthodes de conception distinctes et doivent être pris en compte tout au long du cycle de développement de l’IA.

We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time.

As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology

The strengthening of linear relaxations and bounds of mixed integer linear programs has been an active research topic for decades. Enumeration-based methods for integer programming like linear programming-based branch-and-bound exploit strong dual bounds to fathom unpromising regions of the feasible space. In this talk, we consider the strengthening of linear programs via a composite of Dantzig-Wolfe and Fenchel decompositions. We will start with some geometric interpretations of these two classical methods. Motivated by these geometric interpretations, we will then introduce a novel approach for solving Fenchel sub-problems and introduce a novel decomposition combining Dantzig-Wolfe and Fenchel decompositions in an original manner. Our computational campaign demonstrates very promising results of the new approach when applied to the unsplittable flow problem.

An //orientation// $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a //$k$-orientation// if the in-degree of each vertex in $D$ is at most $k$. An orientation $D$ of $G$ is //proper// if any two adjacent vertices have different in-degrees in $D$. The //proper orientation number// of a graph $G$, denoted by $po(G)$, is the minimum $k$ such that $G$ has a proper $k$-orientation.

A //weighted orientation// of a graph $G$ is a pair $(D,w)$, where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A(D) \to \mathbb{N}\setminus\{0\}$. A //semi-proper orientation// of $G$ is a weighted orientation $(D,w)$ of $G$ such that for every two adjacent vertices $u$ and $v$ in $G$, we have that $S_{(D,w)}(v)
eq S_{(D,w)}(u) $, where
$S_{(D,w)}(v)$ is the sum of the weights of the arcs in $(D,w)$ with head $v$. For a positive integer $k$, a //semi-proper $k$-orientation// $(D,w)$ of a graph $G$ is a semi-proper orientation of $G$ such that $\max_{v\in V(G)} S_{(D,w)}(v) ≤ k$. The //semi-proper orientation number// of a graph $G$, denoted by $spo(G)$, is the least $k$ such that $G$ has a semi-proper $k$-orientation.

In this work, we first prove that $spo(G) \in \{ω(G)-1,ω(G)\}$ for every split graph $G$, and that, given a split graph $G$, deciding whether $spo(G) = ω(G)-1$ is an $NP$-complete problem. We also show that, for every $k$, there exists a (chordal) graph $G$ and a split subgraph $H$ of $G$ such that $po(G) ≤ k$ and $po(H) = 2k-2$. In the sequel, we show that, for every $n≥ p(p+1)$, $spo(P^{p}_n) = \left\lceil \frac{3}{2}p \right\rceil$, where $P^{p}_n$ is the $p^{th}$ power of the path on $n$ vertices. We investigate further unit interval graphs with no big clique: we show that $po(G) ≤ 3$ for any unit interval graph $G$ with $ω(G)=3$, and present a complete characterization of unit interval graphs with $po(G)=ω(G)=3$. Then, we show that deciding whether $spo(G)=ω(G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing $spo(G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$. We also prove that not only computing $spo(G)$, but also $po(G)$, admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size $4^{{\cal O}(k^2)}$ and ${\cal O}(2^kk^2)$, in chordal graphs and split graphs, respectively, for the problem of deciding whether $spo(G)≤ k$ parameterized by $k$. We also present exponential kernels for computing both $po(G)$ and $spo(G)$ parameterized by the value of the solution when $G$ is a cograph. On the other hand, we show that computing $spo(G)$ does not admit a polynomial kernel parameterized by the value of the solution when $G$ is a chordal graph, unless NP $\subseteq$ coNP/poly.

Joint work with F. Havet, C. Linhares Sales, N. Nisse and K. Suchan.

A total matching of a graph G = (V, E) is a subset of G such that its elements, i.e. vertices and edges, are pairwise not adjacent. In this context, the Total Matching Problem calls for a total matching of maximum size. This problem generalizes both the Stable Set Problem,
where we look for a stable set of maximum size, and the Matching Problem, where instead we look for a matching of maximum size. In this talk, we present a polyhedral approach to the Total Matching Problem, and hence, we introduce the corresponding polytope, namely the Total Matching Polytope. To this end, we will present several families of nontrivial valid inequalities that are facet-defining for the Total Matching Polytope. In addition, we provide a first linear complete description for trees and complete bipartite graphs. For the latter family, the complete characterization is obtained by projecting a higher-dimension polytope
onto the original space. This leads to also an extended formulation of compact size for the Total Matching Polytope of complete bipartite graphs. Another problem related to the Total Matching Problem is the Total Coloring Problem. Any partition of the elements into total matchings induces a coloring of G, that is, each total matching is assigned to a color class. Hence, a total coloring is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the endpoints and the edge itself receive different colors. To this end, we propose Integer Linear Program-
ming models for Total Coloring problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Finally, we present computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem.

De nos jours, le concept de Green IT gagne en importance dans le domaine informatique. Bien que les équipes OPS soient généralement attentives à cette problématique, les équipes de développement la maîtrisent souvent moins bien.
Dans le cadre de ce séminaire, je vais vous présenter mes travaux portant sur la mesure de la consommation énergétique d’application. Au cours de mes travaux j’ai cherché à prendre en compte les langages de programmation, le framework utilisé, les options de compilation, l’architecture et l’infrastructure utilisés.
De plus, je vous présenterai la plateforme ENRICO, qui a pour objectif d’évaluer l’impact des nouvelles fonctionnalités en cours de développement, en intégrant les mesures dans le pipeline de CI/CD et de proposer des recommandations de modifications d’implémentation pour réduire les impacts de l’application.

We prove the existence of a computable function f : N → N such that for every integer k and every digraph D either contains a collection C of directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S ⊆ V (D) of size at most f(k) such that D − S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time $g(k)\cdot n^{O(1)}$ for some computable function g : N → N.
Our result unites two deep fields of research from the algorithmic theory for digraphs: The study of the Erdős-Pósa property of digraphs and the study of the Even Dicycle Problem. The latter is the decision problem which asks if a given digraph contains an even dicycle and can be traced back to a question of Pólya from 1913. It remained open until a polynomial time algorithm was finally found by Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997). The Even Dicycle Problem is equivalent to the recognition problem of Pfaffian bipartite graphs and has applications even beyond discrete mathematics and theoretical computer science. On the other hand, Younger’s Conjecture (1973), states that dicycles have the Erdős-Pósa property. The conjecture was proven more than two decades later by Reed, Robertson, Seymour, and Thomas (Combinatorica 1996) and opened the path for structural digraph theory as well as the algorithmic study of the directed feedback vertex set problem. Our approach builds upon the techniques used to resolve both problems and combines them into a powerful structural theorem that yields further algorithmic applications for other prominent problems.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and
Sebastian Wiederrecht

TBA

TBA

TBA