LAMSADE

📖 New LAMSADE paper: NutriKG - un graphe de connaissances pour modéliser les préférences et les besoins nutritionnels. (IC) https://hal.science/hal-05189813v2/document

📖 New LAMSADE paper: Worst-case fair guarantees when spending a common budget. (Theor. Comput. Sci.) https://doi.org/10.1016/j.tcs.2025.115322

Predictive Process Monitoring Using Object-Centric Graph Embeddings Object-centric predictive process monitoring explores and utilizes object-centric event logs to enhance process predictions. The main challenge lies in extracting relevant information and building effective models. In this paper, we propose an end-to-end model that...

📖 New LAMSADE paper: Predictive Process Monitoring Using Object-Centric Graph Embeddings. (ICSOC Workshops (1)) https://doi.org/10.1007/978-981-96-7238-7_5

📖 New LAMSADE paper: Learning Real-Life Approval Elections. (AAMAS) https://dl.acm.org/doi/10.5555/3709347.3743587

📖 New LAMSADE paper: Fairness in Cooperative Multi-agent Multi-objective Reinforcement Learning using the Expected Scalarized Return. (AAMAS) https://dl.acm.org/doi/10.5555/3709347.3743906

📖 New LAMSADE paper: Social Ranking for Feature Selection. (AAMAS) https://dl.acm.org/doi/10.5555/3709347.3743932

📖 New LAMSADE paper: Satisfactory Budget Division. (AAMAS) https://dl.acm.org/doi/10.5555/3709347.3743931

📖 New LAMSADE paper: Minimizing Rosenthal's Potential in Monotone Congestion Games. (AAMAS) https://dl.acm.org/doi/10.5555/3709347.3743548

📖 New LAMSADE paper: Relaxed core stability in hedonic games. (Artif. Intell.) https://doi.org/10.1016/j.artint.2025.104394

📖 New LAMSADE preprint: Parameterized Critical Node Cut Revisited. (arXiv) https://doi.org/10.48550/arXiv.2506.23363

📖 New LAMSADE paper: Committee Monotonicity and Proportional Representation for Ranked Preferences. (EC) https://doi.org/10.1145/3736252.3742642

📖 New LAMSADE paper: Computing Lindahl Equilibrium for Public Goods with and without Funding Caps. (EC) https://doi.org/10.1145/3736252.3742510

📖 New LAMSADE paper: Reallocating Wasted Votes in Proportional Parliamentary Elections with Thresholds. (EC) https://doi.org/10.1145/3736252.3742568

📖 New LAMSADE preprint: Lattice Climber Attack: Adversarial attacks for randomized mixtures of classifiers. (arXiv) https://doi.org/10.48550/arXiv.2506.10888

📖 New LAMSADE preprint: Searching Efficient Deep Architectures for Radar Target Detection using Monte-Carlo Tree Search. (arXiv) https://doi.org/10.48550/arXiv.2506.21772

📖 New LAMSADE preprint: ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention. (arXiv) https://doi.org/10.48550/arXiv.2506.11052

📖 New LAMSADE paper: Parameterized Complexity of Segment Routing. (INFOCOM) https://doi.org/10.1109/INFOCOM55648.2025.11044521

Minimum-cardinality global defensive alliances in general graphs - Annals of Operations Research A subset S of vertices of an undirected graph G is a defensive alliance if at least half of the vertices in the closed neighborhood of each vertex of S are in S. A defensive alliance is a global defensive alliance if it is also a dominating set of G. This paper addresses the problem of finding minimum-cardinality global defensive alliances for general graphs. Two integer linear programming formulations are proposed to address this problem, the second one being an improved version of the first one in which the constraints are attempted for tightening with a cubing-time algorithm. Two new lower bounds on the cardinality of a defensive global alliance are proposed: the first one is based on a linear time algorithm and is shown to be tighter than three of the four lower bounds from the literature, and the second one is derived from the linear programming relaxation of the aforementioned integer linear programming formulations of the problem. An upper bound on the global defensive alliance number is obtained using a greedy peeling algorithm that is shown to be at least as good as an upper bound of the literature, however it is also shown that the proposed algorithm may be unable to find an optimal solution for some graphs. Finally, numerical experiments are carried out on the 78 DIMACS instances and on 75 Erdős-Rényi graphs with up to 10,000 vertices in order to show the effectiveness of the proposed approaches.

📖 New LAMSADE paper: Minimum-cardinality global defensive alliances in general graphs. (Ann. Oper. Res.) https://doi.org/10.1007/s10479-025-06571-2

La Science taille XX elles Paris/IDF 2025 🔥🔥

Nour ElHouda Ben Ali, doctorante et spécialiste en #IA veille à concevoir des algorithmes éthiques et transparents au sein de @psl-univ.bsky.social 🖥️📚

Avec Nour, l’IA trouve sa voix ! 👉 www.paris-centre.cnrs.fr/fr/personne/...

The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra - Journal of Combinatorial Optimization This paper deals with a variant of the Traveling Salesman Problem (TSP), called the Multiple Steiner TSP with Order Constraints (MSTSPOC). Consider an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals. The MSTSPOC consists in finding a minimum-weight subgraph containing for each salesman a tour going in order through its terminals. We study the polytope associated with the Integer Linear Programming (ILP) formulation proposed in Borne et al. (2013). We characterize when the basic inequalities define facets. We also describe new valid inequalities along with necessary conditions and sufficient conditions for these inequalities to be facet-defining. Further families of valid inequalities, coming from closely related problems, are also discussed. The theoretical results presented in this paper are computationally tested in a companion paper (Taktak 2024).

📖 New LAMSADE paper: The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra. (J. Comb. Optim.) https://doi.org/10.1007/s10878-025-01288-1

📖 New LAMSADE paper: Condorcet-consistent choice among three candidates. (Games Econ. Behav.) https://doi.org/10.1016/j.geb.2025.05.005

📖 New LAMSADE paper: A characterization of positive spanning sets with ties to strongly edge-connected digraphs. (Discret. Appl. Math.) https://doi.org/10.1016/j.dam.2025.05.025

📖 New LAMSADE paper: JTutor: JSON Schema Validation Explained. (DBPL) https://doi.org/10.1145/3735106.3736532

📖 New LAMSADE preprint: An Ecosystem of Services for FAIR Computational Workflows. (arXiv) https://doi.org/10.48550/arXiv.2505.15988

📖 New LAMSADE preprint: Study and improvement of search algorithms in two-players perfect information games. (arXiv) https://doi.org/10.48550/arXiv.2505.09639

📖 New LAMSADE preprint: Probability of a Condorcet Winner for Large Electorates: An Analytic Combinatorics Approach. (arXiv) https://doi.org/10.48550/arXiv.2505.06028

📖 New LAMSADE paper: Gaussian Pre-Activations in Neural Networks: Myth or Reality? (Trans. Mach. Learn. Res.) https://openreview.net/forum?id=goe6fv6iSh

Navigating and Exploring Software Dependency Graphs Using Goblin Using package managers is a simple and common method for reusing code through project dependencies. However, these, direct, dependencies can themselves rely on additional packages, resulting in indirect dependencies. It may then become complex to get a grasp of the whole set of dependencies of a project. Beyond studying individual projects, a deep understanding of software ecosystems is also a critical prerequisite for achieving sustained success in software development. This paper presents the 2025 edition of the MSR conference mining challenge. This year’s mining challenge focuses on dependencies and dependency ecosystem analysis using the Goblin framework that has been presented at the previous edition of the MSR conference. Goblin is composed of a Neo4j Maven Central dependency graph and a tool called Weaver for on-demand metric weaving into dependency graphs. As a whole, Goblin is a customizable framework for ecosystem and dependency analysis.

📖 New LAMSADE paper: Navigating and Exploring Software Dependency Graphs Using Goblin. (MSR) https://doi.org/10.1109/MSR66628.2025.00029

📖 New LAMSADE preprint: Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem. (arXiv) https://doi.org/10.48550/arXiv.2505.08451

📖 New LAMSADE paper: Geometry-Aware visualization of high dimensional Symmetric Positive Definite matrices. (Trans. Mach. Learn. Res.) https://openreview.net/forum?id=DYCSRf3vby