Monday 8 January
8
|
Tuesday 9 January
9
|
Wednesday 10 January
10
|
Thursday 11 January
11
-
10 h 00 min – 11 h 00 min
Raul Wayne Teixeira Lopes, «New Menger-like dualities in digraphs and applications to half-integral linkages»
10 h 00 min – 11 h 00 min Raul Wayne Teixeira Lopes, «New Menger-like dualities in digraphs and applications to half-integral linkages» E.3.24 Bâtiment 4 LIRMM 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
-
15 h 00 min
Francois Lamothe, «On the integration of Dantzig-Wolfe and Fenchel decompositions via directional normalizations»
15 h 00 min – 15 h 00 min Francois Lamothe, «On the integration of Dantzig-Wolfe and Fenchel decompositions via directional normalizations» E3.23 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.
|
Friday 12 January
12
|
Saturday 13 January
13
|
Sunday 14 January
14
|
Monday 15 January
15
|
Tuesday 16 January
16
|
Wednesday 17 January
17
|
Thursday 18 January
18
-
10 h 00 min – 11 h 00 min
Júlio Araújo, «Semi-proper orientations of dense graphs»
10 h 00 min – 11 h 00 min Júlio Araújo, «Semi-proper orientations of dense graphs» E.3.24 Bâtiment 4 LIRMM 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.
-
15 h 00 min
Luca Ferrarrini, «Polyhedral Approach to Total Matching and Total Coloring Problems»
15 h 00 min – 15 h 00 min Luca Ferrarrini, «Polyhedral Approach to Total Matching and Total Coloring Problems» E3.23 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.
|
Friday 19 January
19
-
14 h 00 min – 16 h 00 min
Benoit Lange, «De l’optimisation énergétique du bâtiment au Green IT»
14 h 00 min – 16 h 00 min Benoit Lange, «De l’optimisation énergétique du bâtiment au Green IT» Bât.4 - E3.24 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.
|
Saturday 20 January
20
|
Sunday 21 January
21
|