Nous etudions la fonction de Artin qui apparait dans la version forte du theoreme d'approximation de Artin. Nous montrons que cette fonction n'est en general pas majoree par une fonction affine comme cela a ete conjecture. Nous faisons le lien avec un resultat d'approximation diophantienne dans le corps des series en plusieurs variables.

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;²)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

The example based processing problem can be expressed as: "Given an example of an image or video before and after processing, apply a similar processing to a new image or video". Our thesis is that there are some problems where a single general algorithm can be used to create varieties of outputs, solely by presenting examples of what is desired to the algorithm. This is valuable if the algorithm to produce the output is non-obvious, e.g. an algorithm to emulate an example painting's style. We limit our investigations to example based processing of images, video, and 3D models as these data types are easy to acquire and experiment with. We represent this problem first as a texture synthesis influenced sampling problem, where the idea is to form feature vectors representative of the data and then sample them coherently to synthesize a plausible output for the new image or video. Grounding the problem in this manner is useful as both problems involve learning the structure of training data under some assumptions to sample it properly. We then reduce the problem to a labeling problem to perform example based processing in a more generalized and principled manner than earlier techniques. This allows us to perform a different estimation of what the output should be by approximating the optimal (and possibly not known) solution through a different approach.

According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to &#64257;nd good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems. We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the &#64257;rst systematic investigation of this new but important approximation class. We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices. We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the &#64257;rst time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.

In this thesis, we use multitype Galton-Watson branching processes in random environments as individual-based models for the evolution of structured populations with both demographic stochasticity and environmental stochasticity, and investigate the phenotype allocation problem. We explore a variational characterization for the stochastic evolution of a structured population modeled by a multitype Galton-Watson branching process. When the population under consideration is large and the time scale is fast, we deduce the continuous approximation for multitype Markov branching processes in random environments. Many problems in evolutionary biology involve the allocation of some limited resource among several investments. It is often of interest to know whether, and how, allocation strategies can be optimized for the evolution of a structured population with randomness. In our work, the investments represent different types of offspring, or alternative strategies for allocations to offspring. As payoffs we consider the long-term growth rate, the expected number of descendants with some future discount factor, the extinction probability of the lineage, or the expected survival time. Two different kinds of population randomness are considered: demographic stochasticity and environmental stochasticity. In chapter 2, we solve the allocation problem w.r.t. the above payoff functions in three stochastic population models depending on different kinds of population randomness. Evolution is often understood as an optimization problem, and there is a long tradition to look at evolutionary models from a variational perspective. In chapter 3, we deduce a variational characterization for the stochastic evolution of a structured population modeled by a multitype Galton-Watson branching process. In particular, the so-called retrospective process plays an important role in the description of the equilibrium state used in the variational characterization. We define the retrospective process associated with a multitype Galton-Watson branching process and identify it with the mutation process describing the type evolution along typical lineages of the multitype Galton-Watson branching process. Continuous approximation of branching processes is of both practical and theoretical interest. However, to our knowledge, there is no literature on approximation of multitype branching processes in random environments. In chapter 4, we firstly construct a multitype Markov branching process in a random environment. When conditioned on the random environment, we deduce the Kolmogorov equations and the mean matrix for the conditioned branching process. Then we introduce a parallel mutation-selection Markov branching process in a random environment and analyze its instability property. Finally, we deduce a weak convergence result for a sequence of the parallel Markov branching processes in random environments and give examples for applications.

We are interested in a nonlinear filtering problem motivated by an information-based approach for modelling the dynamic evolution of a portfolio of credit risky securities. We solve this problem by `change of measure method\\\' and show the existence of the density of the unnormalized conditional distribution which is a solution to the Zakai equation. Zakai equation is a linear SPDE which, in general, cannot be solved analytically. We apply Galerkin method to solve it numerically and show the convergence of Galerkin approximation in mean square. Lastly, we design an adaptive Galerkin filter with a basis of Hermite polynomials and we present numerical examples to illustrate the effectiveness of the proposed method. The work is closely related to the paper Frey and Schmidt (2010).

Thèse de doctorat : Mathématiques : Strasbourg 1 : 2007. / Titre provenant de l'écran-titre. Bibliogr. p. 99-100.

In electrical engineering, the designer is often presented with the problem of synthesizing a circuit for which the mathematical specifications are unsuitable for physical realization. Hence, the engineer must approximate as well as possible the prescribed network function by another function which is realizable. This paper describes a new approximation method for solving the problem of realizing passive network transfer functions, where the realization is carried out through the use of passive, reciprocal,lumped, linear, and time-invariant elements.

For K a cubic field with only one real embedding and α, β ϵ K, we show how to construct an increasing sequence {m_n} of positive integers and a subsequence {ψ_n} such that (for some constructible constants γ₁, γ₂ > 0): max{ǁm_nαǁ,ǁm_nβǁ} < [(γ₁)/(m_n^(¹/²))] and ǁψ_nαǁ < γ₂/[ψ_n^(¹/²) log ψ_n] for all n. As a consequence, we have ψ_nǁψ_nαǁǁψ_nβǁ < [(γ₁ γ₂)/(log ψ_n)] for all n, thus giving an effective proof of Littlewood's conjecture for the pair (α, β). Our proofs are elementary and use only standard results from algebraic number theory and the theory of continued fractions.

A generalized approximate hand method of analysis is presented for determining the lateral deflections and internal forces in complex multi-storey structures subject to lateral loading. The buildings may include symmetric or asymmetric combinations of coupled walls, rigid frames, shear walls, wall-frames, rigid frames with central walls, frames with single and multi-storey bracing systems as well as cores that are either open or partially closed by floor beams. The deformations taken into account include bending, axial, shear and torsion. / The analysis is based on the continuous medium technique in which the bents in the structure are replaced by idealized assemblies representing their characteristic modes of behaviour. The proposed method is restricted to structures with uniform geometry up the height and linear elastic behaviour of the structural members. / Design equations are presented for the conventional lateral loading cases: a concentrated load at the top of the structure, a uniformly distributed load, and a triangularly distributed load with maximum intensity at the top. The simplicity of this method allows the sway of a structure, the maximum storey sway and its location in the height of the structure to be determined graphically. This procedure enables not only a rapid estimate of the deflections in the structure but together with an assessment of the internal forces it provides a design office method of comparing the efficiencies of different structural alternatives in the preliminary design of tall building structures.