2026

Heure:	10:30 - 12:00
Lieu:	Salle G205, Université de Villetaneuse
Résumé:	Positive spanning sets and their connections to polyhedra
Description:	Clément Royer Positive spanning sets (PSSs), that span a given space through nonnegative linear combinations, have been successfully employed to design and analyze derivative-free optimization algorithms. Although linear algebra is a natural framework for studying PSSs, polyhedral geometry can provide additional insights on the structure of PSSs. In this talk, I will first introduce the concept of positive spanning sets, together with its use in derivative-free optimization. I will then focus on the specific case of polyhedral constrained problems, and explain how to generate positive spanning sets that conform to the geometry of those constraints. Finally, I will turn to a perhaps unexpected construction of PSSs of smallest cardinality through polytopes, and discuss several associated open questions. This talk is based on joint works with Denis Cornaz, Sébastien Kerleau and Lindon Roberts.

Heure:	14:00 - 16:00
Lieu:	Salle G202, Université de Villetaneuse
Résumé:	Warm-Starting QAOA for Combinatorial Optimization via Difference-of-Convex Optimization - A Case Study on Max-Cut
Description:	Viet Hung Nguyen The Quantum Approximate Optimization Algorithm (QAOA) has recently been proposed as a heuristic framework for solving combinatorial optimization problems through a hybrid classical–quantum optimization procedure. The algorithm alternates parameterized quantum transformations with a classical optimization step that adjusts the circuit parameters in order to increase the probability of sampling high-quality solutions. A key factor influencing the performance of QAOA is the choice of the initial state. In standard implementations, the algorithm starts from a uniform superposition over all candidate solutions, which does not exploit structural information about the original optimization problem and may lead to inefficient parameter optimization and lower-quality solutions. In this talk, we propose a warm-start strategy based on continuous optimization, using the Difference-of-Convex Algorithm (DCA). The idea is to exploit a continuous relaxation of the original optimization problem in order to construct an informed initialization that biases the search toward promising regions of the solution space. We illustrate the approach on instances of the Max-Cut problem and show that this strategy can significantly improve the approximation ratios obtained by QAOA. This is a joint work with HA Huy Phuc Nguyen et TA Anh Son.

Heure:	10:30 - 12:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Approximation Schemes for Planar Graph Connectivity Problems
Description:	Meike Neuwohner The k-Edge-Connected Subgraph problem and the k-Connectivity Augmentation problem are among the most basic Network Design problems and, consequently, have been heavily studied. Due to their approximation hardness, the gold standard in terms of approximation guarantee are strong constant factors. Interestingly, this approximation hardness does not carry over to planar graphs. In particular, the 2-Edge-Connected Subgraph problem admits a PTAS on planar graphs. However, the used techniques are very different from the celebrated Baker’s framework, which is a standard way to design PTASs for planar graphs. The main obstacle of using Baker’s technique in its classical form is that it requires a certain locality of the problem. However, k-edge/vertex-connectivity are global properties. We present a novel, and arguably clean, way to extend Baker’s framework to deal with larger connectivity requirements. Based on this, we obtain a PTAS for the k-Edge-Connected Subgraph problem and its vertex analog, even with costs, as long as the max-to-min cost ratio is bounded by a constant. Moreover, together with further insights, we obtain a PTAS for the k-Connectivity Augmentation problem in the same cost setting. We complement this with an NP-hardness result for planar augmentation, showing that all our results are essentially tight. This is joint work with Vera Traub and Rico Zenklusen.

Heure:	10:30 - 12:00
Lieu:	Bâtiment Hypatia, "Salle Tour Eiffel", étage 4
Résumé:	Optimizing Networks Across the Device-Edge-Cloud Continuum
Description:	Alberto Ceselli Modern networked systems are no longer confined to centralized infrastructures, but span a continuum from cloud data centers to edge nodes and individual end devices. In this setting, optimally placing and orchestrating virtualized services becomes a critical and complex optimization problem. In this talk, I present a set of recent contributions addressing this class of problems, characterized by: (a) hard decisions on service placement and orchestration of modular applications, (b) scarce and heterogeneous resources, and (c) multi-layer network graphs. I highlight key challenges arising in this context, formulate the underlying combinatorial optimization problems, present solution approaches based on mixed integer programming and decomposition methods, and outline directions for future research.

Heure:	10:30 - 12:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Integer programs with bounded subdeterminants: solving structured cases
Description:	Stefan Kober It is a notorious open question whether integer programs (IPs), with an integer constraint matrix M whose subdeterminants are all bounded by a constant in absolute value, can be solved in polynomial time. We give an overview on recent progress towards this question and the rich combinatorial structures hidden within. Further, we show how to solve such IPs if the constraint matrix fulfills certain further structural conditions. This talk is based on the following papers: Aprile, M., Fiorini, S., Joret, G., Kober, S., Seweryn, M. T., Weltge, S., & Yuditsky, Y. Integer programs with nearly totally unimodular matrices: the cographic case. [SODA 2025] Fiorini, S., Kober, S., Seweryn, M. T., Shantanam, A., & Yuditsky, Y. Face covers and rooted minors in bounded genus graphs. [preprint 2025] Kober, S. Totally ?-Modular IPs with Two Non-zeros in Most Rows. [IPCO 2025]