**lundi 3 juillet 2017, 14h, D 102 : Roland Grappe (LIPN) :
Mostly box-integer polyhedra and equimodular matrices
**

A polyhedron is box-integer if its intersection with any integer box is a integer polyhedron. We introduce mostly box-integer polyhedra : they are the polyhedra whose dilatations are box-integer as soon as they are integer.

In order to characterize them, we define an equimodular matrix to be a full row rank kxn matrix whose kxk nonzero determinants all have the same absolute value. Among other things, we prove that a polyhedron is mostly box-integer if and only if all its face-defining matrices are equimodular.

We apply this result in integer optimization as follows. Box-TDI polyhedra are well-known polyhedra which can be described by linear systems with strong integrality properties. We prove that a polyhedron is box-TDI if and only if it is mostly box-integer. This yields several new characterizations of box-TDI polyhedra.

**lundi 10 juillet 2017, 14h, A 403 : Jon Lee ( University of Michigan) :
A geometric view of some relaxations in non-convex optimization
**

Convex relaxation is at the heart of general-purpose methods for dealing with non-convexities in optimization. Non-convexities take many forms (e.g., integrality and non-convex low-dimensional functions). We will look at some relaxations and seek to understand the fundamental trade off of tightness vs lightness via a geometric approach. In particular, we will look in some detail at : (i) facility-location problems, and (ii) graph problems (in particular, packing and boolean-quadric/cut problems).

**lundi 26 juin 2017, 14h, A 304 : StÃ©phane Canu (LITIS) :
Variable selection and outlier detection as a MIP
**

(sÃ©minaire commun avec le pÃ´le 3)

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.

**lundi 12 juin 2017, 14h, A403 : Emily Speakman (University of Michigan) :
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.

**jeudi 11 mai 2017 (attention jour inhabituel), 14h, A 305 : Giorgio Lucarelli (INRIA and LIG.) :
A primal-dual approach for online scheduling with resource augmentation
**

A well-identified issue in algorithms and, in particular, in online computation is the weakness of the worst case paradigm. Several more accurate models have been proposed in the direction of eliminating this weakness. Resource augmentation is one of these models which has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to it, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this context, we propose algorithms for online scheduling problems for minimizing variations of the total weighted flow time objective based on mathematical programming and a primal-dual scheme.

**vendredi 28 avril 2017 (attention jour inhabituel), 14h15, D120 : Edouard Bonnet (Middlesex University (Londres)) :
Subexponential algorithms in non sparse classes of graphs
**

Abstract :

Many optimisation problems, while they remain NP-hard on planar graphs, admit subexponential algorithms running in time $2^*O(\sqrt n)*$.

The latter fact is due to a classical result of Lipton and Tarjan that planar graphs have balanced vertex-separators of order $\sqrt n$.

This often allows a divide-and-conquer approach based on exhaustively guessing what an optimum solution does on this small separator.

Actually, an idea of Demaine, Fomin, Hajiaghayi, and Thilikos called bidimensionality even yields algorithms running in time $2^*O(\sqrt k)* n^*O(1)*$

where $k$ is the size of the solution, for most problems, not only on planar graphs but on other sparse classes of graphs such as graphs excluding

a fixed minor.

In this talk, we move away from planar graphs and consider the next best thing in terms of structure :

**geometric graphs** such as intersection graphs or visibility graphs ; and ask the same question of the** existence of subexponential algorithms**.

We survey recent algorithmic results and ETH-based lower bounds (where ETH, the Exponential Time Hypothesis, is the assumption that 3-SAT

has no subexponential algorithm in time $2^*o(n)*$).

Our focus will be whether algorithms running in time** $2^ O(\sqrt n)$ or $n^O(\sqrt k)$** are possible or if, on the contrary,

**no $2^**

or $n^is likely to be obtained.

*o(n)*$or $n^

*o(k)*$**jeudi 20 avril 2017 (attention jour inhabituel), 13h30, C110 : AurÃ©lie Lagoutte (G-SCOP) :
From extended formulations of polytopes to the Clique-Stable Set Separation problem.
**

The concept of extended formulations of polytopes was introduced by Yannakakis. A polytope P has a small extended formulation if it is the projection of a polytope Q lying in a higher dimensional space, with a small number of facets. In particular, he studies the stable set polytope and focus on the case of perfect graphs, where it can be fully described with the clique constraints. He highlights a lower bound stated as a communication complexity problem : Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A certificate for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. The goal is to find a Clique-Stable set separator, i.e. a set F of certificates which contains every useful bipartitions, and with |F|=poly(|V(G)|). This is not possible in general [Goos15], but Yannakakisâ€™ question on perfect graphs is still also open.

We use different techniques to prove that such a polynomial Clique-Stable set separator exists in restricted classes of graphs : probabilistic arguments for random graphs,

VC-dimension for graphs where a split graph H is forbidden, connections with the Erdos-Hajnal property for graphs with no induced path on k vertices and its complement, and decomposition theorem for perfect graphs with no balanced skew partition, and other classes admitting a decomposition theorem.

**Lundi 3 avril 2017, 14h, P 301 : Valentin Garnero (INRIA COATI) :
On augmenting matchings via bounded-length augmentations
**

In a graph, it is well-known that a matching can be turned into a bigger matching by applying a so-called augmentation operation. Due to a classical result of Berge, by repeatedly applying this operation, we actually necessarily end up with a maximum matching.

Nisse, Salch and Weber considered the influence on this fact of restricting the length k of the augmented paths. In particular, they proved that, for k = 3, reaching, via augmentations of (â‰¤ k)-paths, a maximum matching from an initial matching can be done in polynomial time for any graph, while the same problem for any k â‰¥ 5 is NP-complete. The latter result remains true for bipartite graphs, while we still have no clue for trees. Nisse, Salch and Weber nevertheless exhibited a polynomial-time algorithm solving this problem for any path.

In a recent work with Bensmail and Nisse, we made some progress towards understanding this problem for general trees. In particular, we have exhibited polynomial-time solving algorithms for a few more tree classes, including bounded-degree trees, caterpillars, subdivided stars, and trees where the vertices with degree at least 3 are sufficiently far apart. We have also obtained some negative results for modified versions of the problem.

During this talk, we will present the proofs of some of these results, and mention some remaining open questions.

**Lundi 27 mars 2017, 14h, B203 : Valia Mitsou (LIRIS, Lyon1) :
On the complexity of defective coloring
**

In defective coloring, we are given a graph G and two integers c, âˆ†* and are asked if we can c-color G so that the maximum degree induced by any color class is at most âˆ†*. We will present some algorithmic and complexity results on this problem in classes of graphs where proper coloring is easy : on the one hand, we will consider (sub)classes of perfect graphs, namely cographs and chordal graphs ; on the other hand we will talk about structural parameterizations, such as treewidth and feedback vertex set.

**Lundi 20 mars 2017, 14h, A707 : Dimitri Watel (ENSIEE) :
Mutualisation de taxis avec partage de coÃ»t : modÃ©lisation, complexitÃ©, complexitÃ© paramÃ©trÃ©e et rÃ©solution pratique du problÃ¨me
**

(Travaux en collaboration avec Alain Faye)

On se propose dans cette prÃ©sentation dâ€™Ã©tudier une variante du problÃ¨me Dial-A-Ride (DARP). Dans le problÃ¨me original, on cherche Ã optimiser les routes de vÃ©hicules chargÃ©s de transporter des personnes depuis leurs origines respectives vers leurs destinations respectives, tout en respectant des contraintes de fenÃªtre de temps et des contraintes de capacitÃ©s (nombre de places dans le vÃ©hicule). Ce modÃ¨le est gÃ©nÃ©ralement utilisÃ© pour optimiser des chemins pour des taxis. Nous nous penchons sur une variante de ce problÃ¨me dans laquelle les clients partagent le coÃ»t des trajets (ou des parties de trajets) qu’ils effectuent avec d’autres clients. L’objectif est de rÃ©duire le coÃ»t de chaque client d’un facteur au moins Ã©gal Ã alpha.

La prÃ©sentation se dÃ©coupe en deux parties : une Ã©tude thÃ©orique oÃ¹ nous cherchons Ã dÃ©terminer la complexitÃ© paramÃ©trÃ©e vis-Ã -vis des divers paramÃ¨tres naturels du problÃ¨me et une seconde partie oÃ¹ une heuristique d’Ã©numÃ©ration est prÃ©sentÃ©e, accompagnÃ©e de rÃ©sultats de tests sur des donnÃ©es rÃ©elles.

**Lundi 13 mars 2017, 14h, A707 : Nicolas Gastineau (LAMSADE) :
Packing coloring and subcubic graph
**

An i-packing is a subset X_i of vertices such that any two vertices u and v satisfy d(u,v)>i (where d(u,v) is the distance between u and v). The packing chromatic number is the smallest integer such that there exist k sets of vertices X_1,...,X_k forming a partition of the vertex set of a graph, X_i being an i-packing. In this talk, I will first present decision problems about the existence of i-packings and about the packing chromatic number and their computational complexity. Afterwards, I will present conjectures about graphs having bounded packing chromatic number and about subcubic graphs. These conjectures will be motivated by properties on packing chromatic number.

**Lundi 27 fÃ©vrier 2017, 14h15, D 102 : Maximilien Danisch (Telecom ParisTech) :
Towards real-world graph algorithmics
**

Real-world graphs (a.k.a. complex networks) are ubiquitous : the web, Facebook, Twitter, brain networks, protein interaction networks, etc. Studying these graphs and solving computational problems on them (say maximum clique, partitioning or dense subgraph) has applications in many fields. I will first show that the structure of some real-world graphs is special. In particular, they are not adversarial and some difficult problems (say NP-complete or NP-hard problems) can be solved on some huge real-world graphs (say 2G edges or more). I will then present two works along the lines of “understanding and leveraging the structure of real-world graphs in order to build better algorithms” : (i) Enumerating all k-cliques and (ii) Computing the density-friendly graph decomposition.

**Lundi 9 janvier 2017, 14h, A707 : Zsolt Tuza (Hungarian Academy of Sciences, Budapest, and University of Pannonia, Veszprem) : Scheduling, graph coloring, and approximation
**

Joint work with Gyorgy Dosa (University of Pannonia) and Hans Kellerer (University of Graz)

We consider problems of scheduling jobs on a given number of machines,

with some further restrictions on the assignments. The objective is to

minimize the makespan, i.e., to finish all jobs as soon as possible.

Some variants are solvable in polynomial time via matching and network

flow methods, while others are NP-hard. A natural subproblem leads to

the chromatic number of graphs whose independence number is equal to 3.

We prove that this problem is APX-complete, i.e. there exists a constant

c>0 such that a polynomial-time (1+c)-approximation algorithm does not

exist, unless P=NP (while the number of vertices is a trivial

3-approximation for the optimum).

**Lundi 12 dÃ©cembre 2016, 14h, P 301 : Hang Zhou (Max-Planck-Institut fÃ¼r Informatik) : Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs
**

In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or âˆ’ according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible.

In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R union S.

For planar graphs, we prove that correlation clustering reduces to t:m clX_k form%its l='ext2'sN'tl pective based onains evej, and approximaP' />p K hretion Cltion Mae neuivial