The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...
We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...
Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...
Reduced-order models are indispensable for multi-query or real-time problems. However, there are still many challenges to constructing efficient ROMs for time-dependent parametrized problems. Using a linear reduced space is inefficient for time-dependent n ...
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
In the domains of machine learning, data science and signal processing, graph or network data, is becoming increasingly popular. It represents a large portion of the data in computer, transportation systems, energy networks, social, biological, and other s ...
We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...
K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...
Many engineering fields rely on frequency-domain dynamical systems for the mathematical modeling of physical (electrical/mechanical/etc.) structures. With the growing need for more accurate and reliable results, the computational burden incurred by frequen ...
Graphs offer a simple yet meaningful representation of relationships between data. This
representation is often used in machine learning algorithms in order to incorporate structural
or geometric information about data. However, it can also be used in an i ...
We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the Eur ...
This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algo ...
Both numerical simulations and data-driven methods have been applied in dam's displacement modeling. For monitored displacement data-driven methods, the physical mechanism and structural correlations were rarely discussed. In order to take the spatial and ...
Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi ...
The homotopy continuation method has been widely used to compute multiple solutions of nonlinear differential equations, but the computational cost grows exponentially based on the traditional finite difference and finite element discretizations. In this w ...
The present work deals with rational model order reduction methods based on the single-point Least-Square (LS) Padé approximation techniques introduced in Bonizzoni et al. (ESAIM Math. Model. Numer. Anal., 52(4), 1261–1284 2018, Math. Comput. 89, 1229–1257 ...
Popular clustering algorithms based on usual distance functions (e.g., the Euclidean distance) often suffer in high dimension, low sample size (HDLSS) situations, where concentration of pairwise distances and violation of neighborhood structure have advers ...
Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...
Testing for equality of two high-dimensional distributions is a challenging problem, and this becomes even more challenging when the sample size is small. Over the last few decades, several graph-based two-sample tests have been proposed in the literature, ...
In this paper we construct an explicit interpolation formula for Schwartz functions on the real line. The formula expresses the value of a function at any given point in terms of the values of the function and its Fourier transform on the set {0,+/- 1,+/- ...
