HAL : Dernières publications

• [hal-03454237] A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

  It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexity of these recently proposed methods still degrade exponentially with the dimension. In this paper, thanks to an infinitedimensional sum-of-squares representation, we derive a statistical estimator of smooth optimal transport which achieves a precision ε fromÕ(ε −2) independent and identically distributed samples from the distributions, for a computational cost ofÕ(ε −4) when the smoothness increases, hence yielding dimension-free statistical and computational rates, with potentially exponentially dimension-dependent constants.

• [tel-03451277] Lexique et grammaire des interrogatives indirectes partielles en français

  Cette étude a pour but de décrire le fondement théorique de la classe des compléments propositionnels appelés « propositions interrogatives indirectes partielles » en français (e.g. Je me demande où va Paul), en vue de les intégrer comme compléments « essentiels » dans la description exhaustive des types de phrases simples, dans le cadre du lexique-grammaire défini par Maurice Gross (1975).

• [hal-03447208] Information-theoretic problems of DNA-based storage systems

  Введение: взрывной рост объемов производимой человечеством информации ставит новые фундаментальные задачи, связанные с ее эффективным хранением и доступом к ней. Широко используемые при этом магнитные, оптические и полупроводниковые устройства хранения имеют ряд существенных недостатков, связанных, прежде всего, с ограничениями на объем и долговечность хранения. Одной из возможных альтернатив, активно исследуемой в последние годы, является хранение данных с помощью молекул ДНК. Цель: обзор текущего состояния методов хранения информации с помощью молекул ДНК и связанных теоретико-информационных проблем. Результаты: сделан обзор современного состояния дел в разработке систем ДНК-памяти. Проведен анализ типов ошибок, возникающих в таких системах, и корректирующих кодов для выявления и исправления этих ошибок. Показаны недостатки предложенных на сегодня кодов и указаны возможные направления их улучшения. Приведен анализ существующих теоретико-информационных моделей каналов для систем ДНК-памяти и присущих им ограничений. В заключении обзора сформулированы основные проблемы на пути создания практических систем ДНК-памяти, решению которых послужит дальнейшее развитие теоретико-информационных методов, рассмотренных в настоящем обзоре. Ключевые слова-системы хранения информации, ДНК-память, каналы передачи информации, пропускная способность канала, ошибки замены, ошибки вставки, ошибки выпадения.

• [hal-03446803] Spectral measures of empirical autocovariance matrices of high dimensional Gaussian stationary processes

  Consider the empirical autocovariance matrix at a given non-zero time lag based on observations from a multivariate complex Gaussian stationary time series. The spectral analysis of these autocovariance matrices can be useful in certain statistical problems, such as those related to testing for white noise. We study the behavior of their spectral measures in the asymptotic regime where the time series dimension and the observation window length both grow to infinity, and at the same rate. Following a general framework in the field of the spectral analysis of large random non-Hermitian matrices, at first the probabilistic behavior of the small singular values of the shifted versions of the autocovariance matrix are obtained. This is then used to infer about the large sample behaviour of the empirical spectral measure of the autocovariance matrices at any lag. Matrix orthogonal polynomials on the unit circle play a crucial role in our study.

• [hal-03442137] Stochastic Subgradient Descent Escapes Active Strict Saddles

  In non-smooth stochastic optimization, we establish the non-convergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold M where the function f has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of f is lower-bounded. We require two conditions on f. The first assumption is a Verdier stratification condition, which is a refinement of the popular Whitney stratification. It allows us to establish a reinforced version of the projection formula of Bolte et.al. for Whitney stratifiable functions, and which is of independent interest. The second assumption, termed the angle condition, allows to control the distance of the iterates to M. When f is weakly convex, our assumptions are generic. Consequently, generically in the class of definable weakly convex functions, the SGD converges to a local minimizer.

• [hal-03432848] New hierarchy-based segmentation layer: towards automatic marker proposal

  Image segmentation is an ill-posed problem by definition, as it is not always possible to automatically select which object appearing in an image is the object of interest. To deal with this issue, prior knowledge in the form of human-given markers can be included in the segmentation pipeline. Even though user interaction can drastically improve segmentation results, it is an expensive resource, and finding ways to reduce human effort on an interactive segmentation loop is of great interest. In this work, we propose a new segmentation layer to be used with deep neural networks, which allows us to create and train in an endto-end fashion a marker creation network. To train the network, we propose a loss function composed of: a segmentation loss using the proposed differentiable segmentation layer; and a set of regularization functions that enforce the desired characteristics on the produced markers. We showed that by using the proposed layer and loss function, we can train the network to automatically generate markers that recover a good segmentation and have desirable shape characteristics. This behavior is observed on the training dataset, as well as on four unseen datasets.

• [hal-00621640] Lexicalisation of grammars with parameterized graphs

  This paper is about the use of a large-coverage syntactic lexicon for text parsing. Our work focuses on the construction of a lexicalized unification grammar using the fine-grained syntactic information encoded in the lexicon-grammar tables built at LADL (France). We present a method to generate this grammar from a hand-built meta-grammar composed of parameterized graphs. For each lexical item in our lexicon, a specialized grammar is generated by resolving the parameters referring to syntactic properties encoded in the lexicon-grammar tables. We also show that our method can be adapted to a more complex lexicon in the form of relational tables.

• [hal-03432633] Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

  We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.

• [hal-03432628] A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals

  [...]

• [hal-03432592] Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries

  [...]

• [hal-03357080] Variation graphique dans les documents d'Ancien Régime : Nouvelles approches scriptométriques

  [...]

• [hal-03425742] Many-Objective Optimization for Diverse Image Generation

  In image generation, where diversity is critical, people can express their preferences by choosing among several proposals. Thus, the image generation system can be refined to satisfy the user's needs. In this paper, we focus on multi-objective optimization as a tool for proposing diverse solutions. Multiobjective optimization is the area of research that deals with optimizing several objective functions simultaneously. In particular, it provides numerous solutions corresponding to trade-offs between different objective functions. The goal is to have enough diversity and quality to satisfy the user. However, in computer vision, the choice of objective functions is part of the problem: typically, we have several criteria, and their mixture approximates what we need. We propose a criterion for quantifying the performance in multi-objective optimization based on cross-validation: when optimizing n−1 of the n criteria, the Pareto front should include at least one good solution for the removed n th criterion. After providing evidence for the validity and usefulness of the proposed criterion, we show that the diversity provided by multiobjective optimization is helpful in diverse image generation, namely super-resolution and inspirational generation.

• [hal-03366097] Extracting Event-related Information from a Corpus Regarding Soil Industrial Pollution

  We study the extraction and reorganization of event-related information in texts regarding industrial pollution. The object is to build a memory of polluted sites that gathers the information about industrial events from various databases and corpora. An industrial event is described through several features as the event trigger, the industrial activity, the institution, the pollutant, etc. In order to efficiently collect information from a large corpus, it is necessary to automatize the information extraction process. To this end, we manually annotated a part of a corpus about soil industrial pollution, then we used it to train information extraction models with deep learning methods. The models we trained achieve 0.76 F-score on event feature extraction. We intend to improve the models and then use them on other text resources to enrich the polluted sites memory with extracted information about industrial events.

• [hal-02900814] Properties of linear spectral statistics of frequency-smoothed estimated spectral coherence matrix of high-dimensional Gaussian time series

  The asymptotic behaviour of Linear Spectral Statistics (LSS) of the smoothed periodogram estimator of the spectral coherency matrix of a complex Gaussian high-dimensional time series (yn) n∈Z with independent components is studied under the asymptotic regime where both the dimension M of y and the smoothing span of the estimator grow to infinity at the same rate. It is established that the estimated spectral coherency matrix is close from the sample covariance matrix of an independent identically N C (0, I M) distributed sequence, and that its empirical eigenvalue distribution converges towards the Marcenko-Pastur distribution. This allows to conclude that each LSS has a deterministic behaviour that can be evaluated explicitely. Using concentration inequalities, it is shown that the order of magnitude of the deviation of each LSS from its deterministic approximation is of the order of M N where N is the sample size. Numerical simulations suggest that these results can be used to test whether a large number of time series are uncorrelated or not.

• [hal-03413413] Reordering a tree according to an order on its leaves

  In this article, we study two problems consisting in reordering a tree to fit with an order on its leaves provided as input, which were earlier introduced in the context of phylogenetic tree comparison for bioinformatics, OTCM and OTDE. The first problem consists in finding an order which minimizes the number of inversions with an input order on the leaves, while the second one consists in removing the minimum number of leaves from the tree to make it consistent with the input order on the remaining leaves. We show that both problems are NP-complete when the maximum degree is not bounded, as well as a problem on tree alignment, answering two questions opened in 2010 by Henning Fernau, Michael Kaufmann and Mathias Poths. We provide a polynomial-time algorithm for OTDE in the case where the maximum degree is bounded by a constant and an FPT algorithm in a parameter lower than the number of leaves to delete. Our results have practical interest not only for bioinformatics but also for digital humanities to evaluate, for example, the consistency of the dendrogram obtained from a hierarchical clustering algorithm with a chronological ordering of its leaves. We explore the possibilities of practical use of our results both on trees obtained by clustering the literary works of French authors and on simulated data.

• [hal-03412799] An Interval Constraint Programming Approach for Quasi Capture Tube Validation

  Proving that the state of a controlled nonlinear system always stays inside a time moving bubble (or capture tube) amounts to proving the inconsistency of a set of nonlinear inequalities in the time-state space. In practice however, even with a good intuition, it is difficult for a human to find such a capture tube except for simple examples. In 2014, Jaulin et al. established properties that support a new interval approach for validating a quasi capture tube, i.e. a candidate tube (with a simple form) from which the mobile system can escape, but into which it enters again before a given time. A quasi capture tube is easy to find in practice for a controlled system. Merging the trajectories originated from the candidate tube yields the smallest capture tube enclosing it. This paper proposes an interval constraint programming solver dedicated to the quasi capture tube validation. The problem is viewed as a differential CSP where the functional variables correspond to the state variables of the system and the constraints define system trajectories that escape from the candidate tube "for ever". The solver performs a branch and contract procedure for computing the trajectories that escape from the candidate tube. If no solution is found, the quasi capture tube is validated and, as a side effect, a corrected smallest capture tube enclosing the quasi one is computed. The approach is experimentally validated on several examples having 2 to 5 degrees of freedom. 2012 ACM Subject Classification Applied computing → Operations research; Mathematics of computing → Ordinary differential equations; Mathematics of computing → Differential algebraic equations; Mathematics of computing → Interval arithmetic; Theory of computation → Constraint and logic programming

• [hal-03388463] Partition Aggregation for Participatory Budgeting

  Recently, Jain et al. [IJCAI, 2019] studied the effect of project interactions in participatory budgeting (PB) by assuming an existing partition of the projects to interaction structures, namely a grouping of the projects into substitution and complementarity groups. Motivated by their study, here we take voter preferences to find such interaction structures. In our model, voters submit interaction structures, and the goal is to find an aggregated structure. Formally, given a set of projects, and partitions of , the task is to aggregate these partitions into one aggregated partition. We consider this partition aggregation task both for substitution structures and for complementarity structures, studying several aggregation methods for each, including utility-based methods and Condorcet-based methods; we evaluate these methods by analyzing their computational complexity and their behavior with respect to certain relevant axiomatic properties.

• [hal-03400373] Pixel-accurate road crack detection in presence of inaccurate annotations

  Recent road crack detection methods obtain appealing scores but typically allow a few pixel tolerance margin. This is acceptable for locating cracks, but not for measuring their width (indicator of the cracks' severity). Our baseline model, U-VGG19, obtains an F-score of 71.77% on CrackForest, which is superior to other approaches when no tolerance is admitted. However, increasing the scores without tolerance is difficult due to inaccurate annotations. We propose a novel synthetic dataset, Syncrack, as a benchmark for the evaluation of training with inaccurate annotations. Our results show that inaccurate annotations have a detrimental impact on the F-measure, decreasing it by up to 20%. To overcome this, we study label noise correction techniques using weakly supervised learning. Training U-VGG19 with these corrected labels improves the results on Syncrack by up to 12%. Obtained results on the CrackForest and Aigle-RN datasets support that these approaches are useful for real-life data too.

• [hal-01617438] A new fuzzy logic based node localization mechanism for Wireless Sensor Networks

  Being aware of the nodes positions is a key issue in order to locate precisely the sensor node, localization is very important information about sensor nodes in wireless sensor network (WSNs). Hence, the precision improvement is a significant issue that allows an effective data transmission between sensor network (SN) in order to save their energy and extend the network lifetime. In this work, we propose and implement a new mechanism for geographic routing. Therefore, the proposed mechanism is relied on a weighted centroid localization technique, where the positions of unknown nodes are calculated using fuzzy logic method. For this, we propose a fuzzy localization algorithm that uses flow measurement through wireless channel to compute the distance separating the anchor and the sensor nodes. Subsequently, our work is based on the centroid algorithm that calculates the position of unknown nodes using fuzzy Mamdani and Sugeno inference system for increasing the accuracy of estimated positions. Once the localization algorithm has detected the location of nodes with unknown position, the proposed mechanism selects effectively the next-elected CH to reduce the energy dissipation of sensor nodes, which leads to an extension of the network lifetime. The main advantages of the proposed mechanism are three folds: the first is to minimize the position error of nodes and reduces the error localization average. The second is to increase the number of packets transmitted to the next hop cluster head (CH) based on the localization algorithm. The third one is to, reduce the energy consumption of nodes and then extends the network lifetime using an efficient selection of next hop CH. The obtained simulation results show that the proposed mechanism outperforms the existing solutions in terms of energy consumption, execution time (localization time) and localization error, similarly for the number of the packets transmitted to the base station.

• [hal-03383335] On the largest singular values of certain large random matrices with application to the estimation of the minimal dimension of the state-space representations of high-dimensional time series

  This paper is devoted to the estimation of the minimal dimension P of the state-space realizations of a high-dimensional time series y, defined as a noisy version (the noise is white and Gaussian) of a useful signal with low rank rational spectral density, in the high-dimensional asymptotic regime where the number of available samples N and the dimension of the time series M converge towards infinity at the same rate. In the classical low-dimensional regime, P is estimated as the number of significant singular values of the empirical autocovariance matrix between the past and the future of y, or as the number of significant estimated canonical correlation coefficients between the past and the future of y. Generalizing large random matrix methods developed in the past to analyze classical spiked models, the behaviour of the above singular values and canonical correlation coefficients is studied in the high-dimensional regime. It is proved that they are smaller than certain thresholds depending on the statistics of the noise, except a finite number of outliers that are due to the useful signal. The number of singular values of the sample autocovariance matrix above the threshold is evaluated, is shown to be almost independent from P in general, and cannot therefore be used to estimate P accurately. In contrast, the number s of canonical correlation coefficients larger than the corresponding threshold is shown to be less than or equal to P, and explicit conditions under which it is equal to P are provided. Under the corresponding assumptions, s is thus a consistent estimate of P in the high-dimensional regime. The core of the paper is the development of the necessary large random matrix tools.

• [hal-03388443] Efficient, robust and effective rank aggregation for massive biological datasets

  Massive biological datasets are available in various sources. To answer a biological question (e.g., ''which are the genes involved in a given disease?''), life scientists query and mine such datasets using various techniques. Each technique provides a list of results usually ranked by importance (e.g., a list of ranked genes). Combining the results obtained by various techniques, that is, combining ranked lists of elements into one list of elements is of paramount importance to help life scientists make the most of various results and prioritize further investigations. Rank aggregation techniques are particularly well-fitted with this context as they take in a set of rankings and provide a consensus, that is, a single ranking which is the ''closest'' to the input rankings. However, (i) the problem of rank aggregation is NP-hard in most cases (using an exact algorithm is currently not possible for more than a few dozens of elements) and (ii) several (possibly very different) exact solutions can be obtained. As answer to (i), many heuristics and approximation algorithms have been proposed. However, heuristics cannot guarantee how far from an exact solution the consensus ranking will be, and the approximation ratio of approximation algorithms dedicated to the problem is fairly high (not less than 3/2). No solution has yet been proposed to help true-users dealing with the problem encountered in point (ii). In this paper we present a complete system able to perform rank aggregation of massive biological datasets. Our solution is efficient as it is based on an original partitioning method making it possible to compute a high-quality consensus using an exact algorithm in a large number of cases. Our solution is robust as it clearly identifies for the user groups of elements whose relative order is the same in any optimal solution. These features provide answers to points (i) and (ii) and lie in mathematical bases offering guarantees on the computed result. Also, our solution is effective as it has been implemented into a real tool, ConquR-BioV2 is used for the life science community, and evaluated at large-scale using a very large number of datasets.

• [hal-03388474] Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation

  We present a unifying framework encompassing a plethora of social choice settings. Viewing each social choice setting as voting in a suitable metric space, we offer a general model of social choice over metric spaces, in which-similarly to the spatial model of elections-each voter specifies an ideal element of the metric space. The ideal element acts as a vote, where each voter prefers elements that are closer to her ideal element. But it also acts as a proposal, thus making all participants equal not only as voters but also as proposers. We consider Condorcet aggregation and a continuum of solution concepts, ranging from minimizing the sum of distances to minimizing the maximum distance. We study applications of our abstract model to various social choice settings, including single-winner elections, committee elections, participatory budgeting, and participatory legislation. For each setting, we compare each solution concept to known voting rules and study various properties of the resulting voting rules. Our framework provides expressive aggregation for a broad range of social choice settings while remaining simple for voters; and may enable a unified and integrated implementation for all these settings, as well as unified extensions such as sybil-resiliency, proxy voting, and deliberative decision making.

• [hal-03388503] Partition Aggregation for Budgeting

  Motivated by certain aggregation tasks related to participatory budgeting, such as clustering projects and modeling project interactions, we study several variants of the following aggregation problem: Given a set P of m projects, and n partitions of P , the task is to aggregate these n partitions into one aggregated partition. We consider several aggregation methods for this setting, including utility-based methods and Condorcet-based methods and evaluate these methods by analyzing their computational complexity and their behavior with respect to certain relevant axiomatic properties.

• [hal-03388489] Disorders and Permutations

  The additive x-disorder of a permutation is the sum of the absolute differences of all pairs of consecutive elements. We show that the additive x-disorder of a permutation of S(n), n ≥ 2, ranges from n − 1 to n 2 /2 − 1, and we give a complete characterization of permutations having extreme such values. Moreover, for any positive integers n and d such that n ≥ 2 and n − 1 ≤ d ≤ n 2 /2 − 1, we propose a linear-time algorithm to compute a permutation π ∈ S(n) with additive x-disorder d.

• [hal-03388451] Sorting by Multi-Cut Rearrangements

  A multi-cut rearrangement of a string S is a string S′ obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string X1⋅X2⋅X3⋅…⋅Xk⋅Xk+1, where X1 and Xk+1 are possibly empty, and (2) rearranging the Xis so as to obtain S′=Xπ(1)⋅Xπ(2)⋅Xπ(3)⋅…⋅Xπ(k+1), π being a permutation on 1,2,…,k+1 satisfying π(1)=1 and π(k+1)=k+1. Given two strings S and T built on the same multiset of characters from an alphabet Σ, the Sorting by Multi-Cut Rearrangements (SMCR) problem asks whether a given number ℓ of k-cut rearrangements suffices to transform S into T. The SMCR problem generalizes several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting of massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint. More precisely, we investigate its classical and parameterized complexity, as well as its approximability, in the general case or when S and T are permutations.

• [hal-03388430] Justified Representation for Perpetual Voting

  We study the social choice setting of perpetual voting where, based on voter preferences, decisions have to be taken over a finite horizon of consecutive points in time (e.g, days). We consider two complementary settings: a Static setting, in which voter preferences remain static over time, and a Dynamic setting, in which voter preferences may change over time. We adapt the well-established Justified Representation and Proportional Justified Representation axioms, commonly used in the social choice literature, to perpetual voting, resulting in two axiomatic variants for the static setting and four variants for the dynamic setting. We show that all of the axioms are always satisfiable, and that simple preference aggregation methods can be used to satisfy the axioms in both cases. We then conduct a large human study (N = 190) aimed at identifying what potential voters (i.e., ordinary people) deem as desirable outcomes in simple perpetual voting settings. Our results show that approximately half of our participants consider different interpretations of fairness that correspond to our axiomatic framework. Taken jointly, our results can be used to help the research community identify appropriate aggregation methods to use in practice. INDEX TERMS Computational social choice, justified representation, perpetual voting.

• [hal-03388424] Decomposing Subcubic Graphs into Claws, Paths or Triangles *

  Let S = {K1,3, K3, P4} be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any non-empty S ⊆ S. The problem is known to be NP-complete for any possible choice of S in general graphs. In this paper, we assume that the input graph is subcubic (i.e. all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S. We identify all polynomial and NP-complete problems in that setting.

• [hal-03388392] Your rugby mates don't need to know your colleagues: Triadic closure with edge colors

  Given an undirected graph G = (V , E) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as weak and strong such that at most k edges are weak and for each induced P 3 in G at least one edge is weak. We study the following generalizations of STC with c different strong edge colors. In Multi-STC an induced P 3 may receive two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may restrict the set of permitted colors for each edge of G. We show that, under the Exponential Time Hypothesis (ETH), Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time 2 o(|V | 2). We proceed with a parameterized complexity analysis in which we extend previous algorithms and kernelizations for STC [11,14] to the three variants or outline the limits of such an extension.

• [hal-03388045] On the enumeration of plane bipolar posets and transversal structures

  We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results, and in particular we prove that the number tn of transversal structures on n + 2 vertices satisfies (for some c > 0) tn ∼ c (27/2) n n −1−π/arccos(7/8) , which also ensures that the associated generating function is not D-finite.

• [hal-03373114] On p/q-recognisable sets

  Let p/q be a rational number. Numeration in base p/q is defined by a function that evaluates each finite word over A_p={0,1,...,p-1} to some rational number. We let N_p/q denote the image of this evaluation function. In particular, N_p/q contains all nonnegative integers and the literature on base p/q usually focuses on the set of words that are evaluated to nonnegative integers; it is a rather chaotic language which is not context-free. On the contrary, we study here the subsets of (N_p/q)^d that are p/q-recognisable, i.e. realised by finite automata over (A_p)^d. First, we give a characterisation of these sets as those definable in a first-order logic, similar to the one given by the B\"uchi-Bruy\`ere Theorem for integer bases numeration systems. Second, we show that the natural order relation and the modulo-q operator are not p/q-recognisable.

• [hal-03372522] An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes

  We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem is NP-hard, even in the restricted case where C is homeomorphic to a surface. It is known that the problem admits an algorithm with running time f (c)n O(c) , where n is the size of the graph G and c is the size of the two-dimensional complex C. In other words, that algorithm is polynomial when C is fixed, but the degree of the polynomial depends on C. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing a deterministic f (c)n 3-time algorithm. We also provide a randomized algorithm with expected running time 2 c O(1) n O(1). Our approach is to reduce to the case where G has bounded branchwidth via an irrelevant vertex method, and to apply dynamic programming. We do not rely on any component of the existing linear-time algorithms for embedding graphs on a fixed surface; the only elaborated tool that we use is an algorithm to compute grid minors.

• [hal-03272963] A new parametrization for independent set reconfiguration and applications to RNA kinetics

  In this paper, we study the Independent Set (IS) reconfiguration problem in graphs. An IS reconfiguration is a scenario transforming an IS L into another IS R, inserting/removing vertices one step at a time while keeping the cardinalities of intermediate sets greater than a specified threshold. We focus on the bipartite variant where only start and end vertices are allowed in intermediate ISs. Our motivation is an application to the RNA energy barrier problem from bioinformatics, for which a natural parameter would be the difference between the initial IS size and the threshold. We first show the para-NP hardness of the problem with respect to this parameter. We then investigate a new parameter, the cardinality range, denoted by ρ which captures the maximum deviation of the reconfiguration scenario from optimal sets (formally, ρ is the maximum difference between the cardinalities of an intermediate IS and an optimal IS). We give two different routes to show that this problem is in XP for ρ: The first is a direct O(n 2)-space, O(n 2ρ+2.5)-time algorithm based on a separation lemma; The second builds on a parameterized equivalence with the directed pathwidth problem, leading to a O(n ρ+1)-space, O(n ρ+2)-time algorithm for the reconfiguration problem through an adaptation of a prior result by Tamaki [20]. This equivalence is an interesting result in its own right, connecting a reconfiguration problem (which is essentially a connectivity problem within a reconfiguration network) with a structural parameter for an auxiliary graph. We demonstrate the practicality of these algorithms, and the relevance of our introduced parameter, by considering the application of our algorithms on random small-degree instances for our problem. Moreover, we reformulate the computation of the energy barrier between two RNA secondary structures, a classic hard problem in computational biology, as an instance of bipartite reconfiguration. Our results on IS reconfiguration thus yield an XP algorithm in O(n ρ+2) for the energy barrier problem, improving upon a partial O(n 2ρ+2.5) algorithm for the problem.

• [hal-03258315] Construction d’une mémoire des sites pollués : Fusion de bases de données et extraction d’événements

  [...]

• [hal-03364975] PCAM: Product of Cross-Attention Matrices for Rigid Registration of Point Clouds

  Rigid registration of point clouds with partial overlaps is a longstanding problem usually solved in two steps: (a) finding correspondences between the point clouds; (b) filtering these correspondences to keep only the most reliable ones to estimate the transformation. Recently, several deep nets have been proposed to solve these steps jointly. We built upon these works and propose PCAM: a neural network whose key element is a pointwise product of crossattention matrices that permits to mix both low-level geometric and high-level contextual information to find point correspondences. These cross-attention matrices also permits the exchange of context information between the point clouds, at each layer, allowing the network construct better matching features within the overlapping regions. The experiments show that PCAM achieves state-of-the-art results among methods which, like us, solve steps (a) and (b) jointly via deepnets. Our code and trained models are available at https://github.com/valeoai/PCAM.

• [hal-03363238] Segmentation de l'arbre vasculaire rétinien : étude de la performance en fonction de l'approche de segmentation

  La segmentation des vaisseaux rétiniens est une étape cruciale pour la détection de plusieurs pathologies oculaires aussi qu'à la détection des autres structures anatomiques rétiniennes. Ce travail présente un état de l'art sur les méthodes de segmentation des vaisseaux rétiniens. De ce fait, une analyse explicite des méthodes est proposée. Ces méthodes sont catégorisées selon les outils mise en pratique. Cette étude a permis de proposer un workflow général des méthodes de segmentation. Par la suite, les démarches d'évaluation des méthodes ont été étudiées et les performances ont été comparées. En outre, les performances ont été synthétisées en fonction de l'utilisation des outils mise en pratique. I.

• [hal-03363234] Computational Efficiency Optimization of Optic Disc Detection in Fundus Image

  The OD detection is a mainly step in many methods for ophthalmic diseases diagnosis. The work described in [7] proposes a performance optic disk detection approach based on blood vessel tracking and optic disk contrast. However, the method is characterized by a higher execution time which is about 10 s in STARE DB images. M oreover, the execution time increases proportionally with the fundus image resolution. This computational performance is a limiting factor to employ the method in diagnosis systems of ophthalmic diseases. This paper aims to optimize the method processing in order to enhance the computational performance. The first contribution consists of optimizing repet itive steps with the aim of reducing times. Thereafter, all processing steps are implemented in GPU architectures. The experimental results indicat e that each one of the contributions insures enhancing computational performance with speedup equal to 1.7 and 2.5, respectively. The implementation with combined contributions leads to a speedup equal to 8.6 which leads to an execution time about 1 second.

• [hal-03360955] A Mathematical Model for Bus Scheduling with Conditional Signal Priority

  Inaccuracy of buses is a common situation. A common practice is that a certain amount of slack is usually added to the schedule of bus operation, so that the bus can execute the schedule in most cases. On the other hand, slack means that buses sometimes have to wait for a while at the station or slow down while driving. Since the bus cannot accelerate the driving process by itself, this method cannot make the bus fully implement the schedule. Researchers invented the Transit signal priority (TSP) and conditional signal priority (CSP), the purpose of which is to give the bus signal priority to speed up when it is delayed to a certain extent. Some previous work has studied the driving process of buses with CSP. However, there is still room for further improvement in the mathematical description of the bus driving process based on CSP. In this article, we analyze the driving state of the bus under different CSP states, that is, positive and negative. Then a series of representative and operational assumptions are given. These assumptions can be used as the basis for future research on such topics. With the assumptions, we give a mathematical model of the bus driving process using CSP. According to some performance indicators of the bus driving process obtained in the modeling process, an optimization goal is established to comprehensively improve the driving effect of the bus. Mathematical analysis and numerical solution verify the applicability of the model.

• [hal-03360839] Stochastic Integrated Supplier Selection and Disruption Risk Assessment Under Ripple Effect

  The impact of the COVID-19 pandemic in the supply chain (SC) evokes the need for valid measures to cope with the SC disruption risk. Supplier selection and disruption risk assessment, as valid measures, have received increasing attentions from academia. However, most of existing works focus on supplier selection and disruption risk assessment separately. This work investigates an integrated supplier selection and disruption risk assessment problem under ripple effect. The objective is to minimize the weighted sum of the disrupted probability and the total cost for the manufacturer. For the problem, a new stochastic programming model combined with Bayesian network (BN) is formulated. Then, an illustrative example is conducted to demonstrate the proposed method.

• [hal-03360830] A Tabu Search Heuristic for the Robust Dynamic Bayesian Network Optimisation Problem Under the Supply Chain Ripple Effect

  Due to the impact of the global COVID-19, supply chain (SC) risk management under the ripple effect is becoming an increasingly hot topic in both practice and research. In our former research, a robust dynamic bayesian network (DBN) approach has been developed for disruption risk assessment, whereas there still exists a gap between the proposed simulated annealing (SA) algorithm and commercial solver in terms of solution quality. To improve the computational efficiency for solving the robust DBN optimisation model, a tabu search heuristic is proposed for the first time in this paper. We design a novel problem-specific neighborhood move to keep the search in feasible solution space. The computational experiments, conducted on randomly generated instances, indicate that the average gap between our approach and commercial solver is within 0.07 %, which validates the performance of the proposed method.

• [hal-03360817] Electric Bus Charging Scheduling Strategy with Stochastic Arrival Time and State of Charge

  To alleviate the range anxiety of drivers and time-consuming charging for electric buses (eBuses), opportunity fast-charging has gradually been utilized. Considering that eBuses have operational tasks, identifying an optimal charging scheduling will be needed. However, in the real world, arrival time and state of charge (SOC) of eBuses are uncertain. Therefore, it is challenging for the charging station to efficiently schedule charging tasks. To solve the problem, this paper develops a two-stage stochastic eBus charging scheduling model. In the first stage, eBuses are assigned to designated chargers. After the arrival time and SOC are realized, the second stage determines the charging sequence of eBuses on each charger. The objective is to minimize the penalty cost of tardiness by determining the charging start time and the corresponding charging duration time. Then, a sample average approximation (SAA) algorithm is applied. Additional numerical experiments are performed to verify the efficiency of the stochastic programming model and algorithm.

• [hal-03360792] A New Robust Dynamic Bayesian Network Model with Bounded Deviation Budget for Disruption Risk Evaluation

  Dynamic Bayesian network (DBN), combining with probability intervals, is a valid tool to estimate the risk of disruptions propagating along the supply chain (SC) under data scarcity. However, since the approach evaluate the risk from the worst-case perspective, the obtained result may be too conservative for some decision makers. To overcome this difficulty, a new robust DBN model, considering bounded deviation budget, is first time to be developed to analyse the disruption risk properly. We first formulate a new robust DBN optimization model with bounded deviation budget. Then a linearization technique is applied to linearize the nonlinear bounded deviation budget constraint. Finally, a case study is conducted to demonstrate the applicability of the proposed model and some managerial insights are drawn.

• [hal-03348490] Fast and efficient retinal blood vessel segmentation method based on deep learning network

  The segmentation of the retinal vascular tree presents a major step for detecting ocular pathologies. The clinical context expects higher segmentation performance with a reduced processing time. For higher accurate segmentation, several automated methods have been based on Deep Learning (DL) networks. However, the used convolutional layers bring to a higher computational complexity and so for execution times. For such need, this work presents a new DL based method for retinal vessel tree segmentation. Our main contribution consists in suggesting a new U-form DL architecture using lightweight convolution blocks in order to preserve a higher segmentation performance while reducing the computational complexity. As a second main contribution, preprocessing and data augmentation steps are proposed with respect to the retinal image and blood vessel characteristics. The proposed method is tested on DRIVE and STARE databases, which can achieve a better trade-off between the retinal blood vessel detection rate and the detection time with average accuracy of 0.978 and 0.98 in 0.59 s and 0.48 s per fundus image on GPU NVIDIA GTX 980 platforms, respectively for DRIVE and STARE database fundus images.

• [hal-03353520] The Corpus for Idiolectal Research (CIDRE)

  It is well known that the idiolect (the language of an individual) evolves over time. However, there is a lack of quantitative studies on this topic, due to the lack of large corpora (but see Barlow 2013; Mollin 2009; Petré et al. 2019 for a few examples). To study what is specific in an idiolect and how it evolves over a lifetime, we assembled, cleaned and dated the fiction works of 11 very prolific 19th and early 20th century French writers. This resulted in the CIDRE corpus counting 37 million words and over 400 books.

• [hal-03348489] Computational aspects of deep learning models for detection of eye retina abnormalities

  Glaucoma, Cataract, Age-related macular degeneration, (AMD) Diabetic retinopathy (DR) are among the leading retinal diseases. Thus, there is an active effort to create and develop methods to automate screening of retinal diseases. Many CAD (Computer Aided Diagnosis) systems have been expanded and are widely used for ocular diseases. Recently, Deep Neural Networks (DNNs) have been adopted in ophthalmology and applied to fundus images, achieving detection of retinal abnormalities using retinal images. There are essentially two approaches, the first one is based on hybrid method that employs image processing for preprocessing, features extraction and post processing and Deep Neural Network (DNN) is only used for classification. The second is the fully method where DNN is used for both feature extraction and classification. Several DNN models and their variants have been proposed such as AlexNet, VGG, GoogleNet, Inception, U-Net, Residual Net (ResNet), DenseNet for detection of eye retina abnormalities. The aim of this work is to provide the background and the methodology to conduct a benchmarking analysis including the computational aspects and analysis of the representative DNNs proposed in the state of the art for detection DR diseases. For each DNN different characteristics and some performance indices (i.e. model complexity, computation complexity, inference time, memory use) and detection disease performance (i.e. accuracy rate), must be taking into account to find the more accurate model. The public domain datasets used for training and testing the DNN models such as Kaggle, MESSIDOR, and EyePACS are outlined and analyzed in particular in DR detection.

• [hal-03346830] Sorting by Multi-cut Rearrangements

  [...]

• [hal-03346823] Sorting by Multi-Cut Rearrangements

  A multi-cut rearrangement of a string S is a string S′ obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string X1·X2·X3·…·Xk·Xk+1, where X1 and Xk+1 are possibly empty, and (2) rearranging the Xis so as to obtain S′=Xπ(1)·Xπ(2)·Xπ(3)·…·Xπ(k+1), π being a permutation on 1,2,…,k+1 satisfying π(1)=1 and π(k+1)=k+1. Given two strings S and T built on the same multiset of characters from an alphabet Σ, the Sorting by Multi-Cut Rearrangements (SMCR) problem asks whether a given number ℓ of k-cut rearrangements suffices to transform S into T. The SMCR problem generalizes several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting of massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint. More precisely, we investigate its classical and parameterized complexity, as well as its approximability, in the general case or when S and T are permutations.

• [hal-03346821] Decomposing subcubic graphs into claws, paths or triangles

  [...]

• [hal-03341803] Evaluating Hierarchical Clustering Methods for Corpora with Chronological Order

  Hierarchical clustering can traditionally be represented through a dendrogram: a rooted tree whose leaves are documents, the length of the path between two leaves representing the stylistic/linguistic distance between the documents. Clusters correspond to branching nodes: the shorter the distance between two nodes, the more they are expected to share stylistic and linguistic features. We wonder how much the resulting dendrogram is consistent with the chronological order of writing. Indeed, this would provide us with a method of evaluating the result of the clustering. More precisely, the question we want to answer is: can the branching nodes of the dendrogram be re-ordered so that its leaves follow a chronological order as best as possible, while of course preserving the structure of the dendrogram?

• [hal-03341682] eHPWAS'21: Ninth International workshop on e-health pervasive wireless applications and services

  [...]

• [hal-03341680] eHPWAS'20: Eighth International workshop on e-health pervasive wireless applications and services

  [...]