Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Computing the fully optimal spanning tree of an ordered bipolar directed graph
No full textInternational audienceIt was previously shown by the authors that a directed graph on a linearly ordered set of edges (ordered graph) with adjacent unique source and sink (bipolar digraph) has a unique fully optimal spanning tree, that satisfies a simple criterion on fundamental cycle/cocycle directions. This result is related to a strengthening of the notion of optimality in linear programming. Furthermore, this result yields, for any ordered graph, a canonical bijection between bipolar orientations and spanning trees with internal activity 1 and external activity 0 in the sense of the Tutte polynomial. This bijection can be extended to all orientations and all spanning trees, yielding the active bijection, presented for graphs in other papers. In this paper, we specifically address the problem of the computation of the fully optimal spanning tree of an ordered bipolar digraph. In contrast with the inverse mapping, built by a straightforward single pass over the edge set, the direct computation is not easy and had previously been left aside. We give two independent constructions. The first one is a deletion/contraction recursion, involving an exponential number of minors. It is structurally significant but it is efficient only for building the whole bijection (i.e., all images) at once. The second one is more complicated and is the main contribution of the paper. It involves just one minor for each edge of the resulting spanning tree, and it is a translation and an adaptation to the case of graphs, in terms of weighted cocycles, of a general geometric linear programming type algorithm, which allows for a polynomial time complexity
Constrained Flows in Networks
No full textInternational audienceThe support of a flow in a network is the subdigraph induced by the arcs for which x_{ij}>0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network has a maximum flow such that the maximum out-degree of the support of is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of deciding the maximum flow we can send from to along 2 paths (called a maximum 2-path-flow) in . Baier et al. (2005) gave a polynomial algorithm which finds a 2-path-flow whose value is at least of the value of a optimum 2-path-flow. This is best possible unless P=NP. They also obtained a -approximation for the maximum value of a -path-flow for every . In this paper we give an algorithm which gets within a factor of the optimum solution, where is the 'th harmonic number (). This improves the approximation bound due to Baier et al. when . We show that in the case where the network is acyclic, we can find a maximum -path-flow in polynomial time for every . We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible
On the Shared Transportation Problem: Computational Hardness and Exact Approach
No full textInternational audienceIn our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the [Formula: see text]-path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm
Impact of the bars behavior on the design of soft tensegrities
No full textTECHNICAL BRIEFSInternational audienceSoft tensegrity is a recent concept, which can be described as a prestressed assembly of soft cables in tension and bars in compression. In this paper, we investigate the impact of the bar behavior on the mechanical properties of a tensegrity. This is achieved through the change of bar material, from soft (e.g., silicone) to stiff (e.g., steel) materials. First, we show that it is possible to make a self-supporting tensegrity where both cables and bars are made of soft material. Second, we highlight that the bar material impacts the isotropy of the stiffness matrix of the tensegrity and the range of achievable stiffness. Lastly, we demonstrate that the bar material has a significant impact on the precision of stiffness variation, when active elements are integrated into the tensegrity. From these effects, we extract design guidelines for the choice of bar material in a soft tensegrity
OpenPiton4HPC: Optimizing OpenPiton Towards High Performance Manycores
No full textInternational audienceIn recent years, numerous multicore RISC-V platforms have emerged. Development frameworks such as OpenPiton are employed in designs that aim to scale to a large number of cores. While OpenPiton presents a large flexibility, supporting different requirements and processing cores, some of its design decisions result in designs that are not optimized for High-Performance Computing (HPC) requirements.This work presents OpenPiton4HPC, an extension and optimization of OpenPiton for high-performance manycores. The key contributions are enabling multiple memory controllers, supporting router bypassing and NoC concentration, adding support for configurable cache sizes and cache block sizes, and allowing configurable bus widths in the NoC and in the cache SRAMs. On a 64-core manycore architecture, these new features and optimizations provide a geometric mean speedup of 7.2x compared to the OpenPiton baseline
Estimation de l'évolution de la pauvreté par apprentissage profond & imagerie satellitaire
No full textThe traditional method for assessing household poverty involves conducting socioeconomic censuses.This method is expensive and requires considerable logistical and human effort.An easier alternative is to use satellite imagery and neural networks to train the latter to extract information from satellite images and automatically correlate it with poverty as measured in socioeconomic censuses.Subsequently, the learned model is used to predict poverty in areas where no survey has been conducted.However, recent studies have observed difficulties in estimating poverty evolution, that is, predicting a quantitative value indicating whether poverty is increasing or decreasing over a given period.One idea to enable the estimation of poverty evolution is to consider satellite image time series and sequence to sequence models.In this context, we used a deep learning sequence to sequence model, namely, the Transformer, for satellite image time series.This model was compared to several purely spatial models (i.e., processing individual satellite images) on the task of estimating changes in nighttime light intensity, which is a classic proxy for several socioeconomic indicators.These experiments were conducted both on targeted geographical areas and on a larger dataset that we constructed, comprising nearly 10,000 satellite image time series over 20 years with one image per year.Evaluations identified that spatio-temporal methods allow for the prediction of nighttime light intensity evolution with an R2 score of up to 0.5 for long-term evolutions, compared to a null R2 for spatial models. These experiments were also conducted on a benchmark dataset for poverty trends, on which comparable results were obtained.La méthode traditionnelle pour évaluer la pauvreté des ménages consiste à mener une enquête de terrain.Cette méthode est onéreuse et demande un effort logistique et humain considérable.Une alternative plus facile à déployer consiste à utiliser l'imagerie satellitaire et les réseaux de neurones pour apprendre ces derniers à extraire l'information des images satellites afin de la corréler automatiquement à la pauvreté mesurée dans les enquêtes de terrain.Dans un second temps, le modèle appris est utilisé pour estimer la pauvreté là où aucune enquête n'a été menée.Néanmoins, des travaux récents observent des difficultés pour estimer l'évolution de la pauvreté, c'est-à-dire, estimer si la pauvreté augmente ou diminue sur une période de temps donnée.Une idée pour permettre d'estimer l'évolution de la pauvreté serait de considérer des séries temporelles d'images satellites, et des modèles d'apprentissage spatio-temporels.Dans ce cadre, nous avons utilisé un modèle d'apprentissage séquence à séquence, le Transformer, que nous avons adapté pour prédire des séries temporelles d'intensités lumineuses nocturne avec des séries temporelles d'images satellites.Ce modèle a été comparé à plusieurs modèles uniquement spatiaux (i.e. traitant des images satellites individuelles), sur la tâche de prédiction de l'évolution de l'intensité lumineuse nocturne, qui est un proxy classique de plusieurs indicateurs socio-économique.Ces expériences ont été menées à la fois sur des zones géographiques ciblées, mais également sur un plus grand jeu de données que nous avons construit, comprenant près de 10 000 séries temporelles d'images satellites de 20 années avec une image par an.Les évaluations ont permis d'identifier que les méthodes spatio-temporelles permettent d'estimer les évolutions de l'ILNs avec un score R2 allant jusqu'à 0.5 pour les évolutions longues, contre un R2 nul pour les modèles spatiaux.Ces expériences ont également été menées sur un jeu de donnée benchmark pour l'évolution de la pauvreté, sur lequel des résultats comparables sont obtenus
On the connections between the spatial Lambda–Fleming–Viot model and other processes for analysing geo-referenced genetic data
No full textInternational audienc
Overview of LifeCLEF 2024 Teaser : Challenges on Species Distribution Prediction and Identification
No full textInternational audienceBuilding accurate knowledge of the identity, the geographic distribution and the evolution of species is essential for the sustainable development of humanity, as well as for biodiversity conservation. However, species identification and inventory is a difficult and costly task, requiring large-scale automated approaches. The LifeCLEF lab has been promoting and evaluating advances in this domain since 2011 through the organization of multi-year challenges. The 2024 edition presented in this article proposes five data-driven challenges as a continuation of this effort: (i) BirdCLEF: bird species recognition in audio soundscapes, (ii)FungiCLEF: fungi recognition beyond 0-1 cost, (iii) GeoLifeCLEF: remote sensing based prediction of species, (iv) PlantCLEF: Multi-species identification in vegetation plot images, and (v) SnakeCLEF: snake recognition in medically important scenarios
Innovative platform for the electrical stimulation and monitoring of 3D muscle tissues
No full textInternational audienc
État de l'art sur les approches en apprentissage par renforcement multi-agent.
No full textInternational audienceIn reinforcement learning, an agent adapts its behavior in order to maximize a reward. These approaches are used to teach an agent how to act in its environment. Major difficulties arise when these approaches are applied to several agents. In this case, directly transposing reinforcement learning approaches is likely to fail. This is why it is interesting to use new approaches specifically adapted to multi-agent systems. This article presents a state-of-the-art review of multi-agent reinforcement learning approaches. The proposed synthesis focuses on the underlying approach rather than on the nature of the algorithms. Its aim is to help identify the best solutions in each context.En apprentissage par renforcement, un agent adapte son comportement afin de maximiser une récompense. Ces approches sont utilisées pour apprendre à un agent comment agir dans son environnement. D’importantes difficultés apparaissent lorsque l’on applique ces approches à plusieurs agents. Dans ce cas-là, directement transposer les approches d’apprentissage par renforcement a de grandes chances d’échouer. Ainsi, il devient intéressant d’utiliser de nouvelles approches spécifiquement adaptées aux systèmes multi-agents. Cet article présente un état de l’art sur les approches d’apprentissage par renforcement multi-agent. La synthèse proposée se focalise sur l’approche sous-jacente plutôt que sur la nature des algorithmes. Elle a pour but d’aider à identifier les meilleures solutions selon le contexte