Résolution de problème

vignette|Résolution d'un problème mathématique. La résolution de problème est le processus d'identification puis de mise en œuvre d'une solution à un problème. Méthodologie Dans l'industrie et l'ingénierie des connaissances

Analyse de cause racine (ACR, Root cause analysis) : cette démarche part du constat qu'il est plus judicieux de traiter les causes d'un problème que d'en traiter les symptômes immédiats. Puisqu'analyser les causes d'un problème permet d'en déterminer une solution définitive, et donc, empêcher qu'il ne se reproduise de nouveau. L’ACR est un processus itératif d'amélioration continue (PDCA, Plan Do Check Act). Elle peut être décomposée en quatre étapes (Processus DIVE, Define Investigate Verify Ensure) ou en huit étapes (Processus 8D).
Méthode Shainin
Creative Problem Solving
Troubleshooting

En informatique

Diviser pour régner (informatique)

En psychologie C'est une notion largement employée dans le vocabulair

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also been numerous works that study combinatorial problems with submodular objective functions. This is motivated by their natural diminishing returns property which is useful in real-world applications. The thesis at hand is concerned with the study of streaming and matching problems with submodular functions.Firstly, motivated by developing robust algorithms, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We study the maximum matching problem and cardinality constrained monotone submodular maximization. We show that even under this seemingly powerful adversary, it is possible to break the barrier of 1/2 for both these problems in the streaming setting. Our main result is a novel streaming algorithm that computes a 0.55-approximation for cardinality constrained monotone submodular maximization.In the second part of the thesis, we study the problem of matroid intersection in the semi-streaming setting. Our main result is a (2 + e)-approximate semi-streaming algorithm for weighted matroid inter- section improving upon the previous best guarantee of 4 + e. While our algorithm is based on the local ratio technique, its analysis differs from the related problem of weighted maximum matching and uses the concept of matroid kernels. We are also able to generalize our results to work for submodular functions by adapting ideas from a recent result by Levin and Wajc (SODA'21) on submodular maximization subject to matching constraints.Finally, we study the submodular Santa Claus problem in the restricted assignment case. The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function fi. The goal is to maximize mini fi(Si) where S1, . . . , Sm is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n1/2+e)-approximation algorithm. In the restricted assignment case, each player is given a set of desired resources Gi and the individual valuation functions are defined as fi(S)= f(SnGi). OurmainresultisaO(loglog(n))-approximation algorithm for the problem. Our proof is inspired by the approach of Bansal and Srividenko (STOC'06) to the Santa Claus problem. Com- pared to the more basic linear setting, the introduction of submodularity requires a much more involved analysis and several new ideas.

EPFL2022

Variational Methods For Continuous-Domain Inverse Problems: the Quest for the Sparsest Solution

Thomas Jean Debarre

The goal of this thesis is to study continuous-domain inverse problems for the reconstruction of sparse signals and to develop efficient algorithms to solve such problems computationally. The task is to recover a signal of interest as a continuous function from a finite number of measurements. This problem being severely ill-posed, we choose to favor sparse reconstructions. We achieve this by formulating an optimization problem with a regularization term involving the total-variation (TV) norm for measures. However, such problems often lead to nonunique solutions, some of which, contrary to expectations, may not be sparse. This requires particular care to assert that we reach a desired sparse solution.Our contributions are divided into three parts. In the first part, we propose exact discretization methods for large classes of TV-based problems with generic measurement operators for one-dimensional signals. Our methods are based on representer theorems that state that our problems have spline solutions. Our approach thus consists in performing an exact discretization of the problems in spline bases, and we propose algorithms which ensure that we reach a desired sparse solution. We then extend this approach to signals that are expressed as a sum of components with different characteristics. We either consider signals whose components are sparse in different bases or signals whose first component is sparse, and the other is smooth. In the second part, we consider more specific TV-based problems and focus on the identification of cases of uniqueness. Moreover, in cases of nonuniqueness, we provide a precise description of the solution set, and more specifically of the sparsest solutions. We then leverage this theoretical study to design efficient algorithms that reach such a solution. In this line, we consider the problem of interpolating one-dimensional data points with second-order TV regularization. We also study this same problem with an added Lipschitz constraint to favor stable solutions. Finally, we consider the problem of the recovery of periodic splines with low-frequency Fourier measurements, which we prove to always have a unique solution.In the third and final part, we apply our sparsity-based frameworks to various real-world problems. Our first application is a method for the fitting of sparse curves to contour data. Finally, we propose an image-reconstruction method for scanning transmission X-ray microscopy.

EPFL2022

Variational Methods For Continuous-Domain Inverse Problems: the Quest for the Sparsest Solution

Thomas Jean Debarre

EPFL2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

EPFL2022

Integrating problem solving and information gathering using constraint satisfaction

Streaming and Matching Problems with Submodular Functions

Variational Methods For Continuous-Domain Inverse Problems: the Quest for the Sparsest Solution

Integrating problem solving and information gathering using constraint satisfaction

Variational Methods For Continuous-Domain Inverse Problems: the Quest for the Sparsest Solution

Streaming and Matching Problems with Submodular Functions