In this work, we deal with fixed interval scheduling problems with the possibility of random delay of the end of the tasks (FIS). First, we pre- sent the basic deterministic FIS problems and ways to solve them. Next, we introduce the concept of minimax and present two well-known and one new FIS problem under uncertainty, when random task delays are conside- red to belong to a certain uncertainty set. Next, we deal with the solution of previously presented FIS problems for five chosen uncertainty sets. We present both previously achieved and original results. The work concludes with a summary of a numerical study of two problems. First, we explore the possibility of Lagrange relaxation application to the first presented problem. Next we explore the quality of approximation allowing to solve the later of problems as LP. 1

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc., ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc. Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas. Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude. Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret. Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement. Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.

No description available.

University, Diss., 1999--Freiburg (Breisgau).

Universiẗat, Diss., 2004--Kassel.

The present paper is devoted to the investigation of the guided wave problem. This problem is formulated as the eigenvalue problem with a compact self-adjoint operator pencil. Applying the minimax principle for the compact operators in the Hilbert space we obtain a necessary and sufficient condition for the existence of a preassigned number of linearly independent guided modes. As a consequence of this result we also derive simple sufficient conditions, which can be easily applied in practice. We give a statement of the problem in a bounded domain and propose an efficient method for solving the problem.

No description available.

This thesis describes the social table game Scrabble, and its realization in the form of computer games. Gradually examines all important aspects that affect the performance of the implementation. Especially after the election of the appropriate data structures retained for the vocabulary, affecting the efficiency of generating moves, and the selection of appropriate algorithms with regard to the maximum speed. There is particular emphasis on artificial intelligence opponent and its ability to compete not only amateurs, but professional SCRABBLE players.

In the present dissertation, we investigate two different nonparametric models; empirical Bayes model and functional deconvolution model. In the case of the nonparametric empirical Bayes estimation, we carried out a complete minimax study. In particular, we derive minimax lower bounds for the risk of the nonparametric empirical Bayes estimator for a general conditional distribution. This result has never been obtained previously. In order to attain optimal convergence rates, we use a wavelet series based empirical Bayes estimator constructed in Pensky and Alotaibi (2005). We propose an adaptive version of this estimator using Lepski’s method and show that the estimator attains optimal convergence rates. The theory is supplemented by numerous examples. Our study of the functional deconvolution model expands results of Pensky and Sapatinas (2009, 2010, 2011) to the case of estimating an (r + 1)-dimensional function or dependent errors. In both cases, we derive minimax lower bounds for the integrated square risk over a wide set of Besov balls and construct adaptive wavelet estimators that attain those optimal convergence rates. In particular, in the case of estimating a periodic (r + 1)-dimensional function, we show that by choosing Besov balls of mixed smoothness, we can avoid the ”curse of dimensionality” and, hence, obtain higher than usual convergence rates when r is large. The study of deconvolution of a multivariate function is motivated by seismic inversion which can be reduced to solution of noisy two-dimensional convolution equations that allow to draw inference on underground layer structures along the chosen profiles. The common practice in seismology is to recover layer structures separately for each profile and then to combine the derived estimates into a two-dimensional function. By studying the two-dimensional version of the model, we demonstrate that this strategy usually leads to estimators which are less accurate than the ones obtained as two-dimensional functional deconvolutions. Finally, we consider a multichannel deconvolution model with long-range dependent Gaussian errors. We do not limit our consideration to a specific type of long-range dependence, rather we assume that the eigenvalues of the covariance matrix of the errors are bounded above and below. We show that convergence rates of the estimators depend on a balance between the smoothness parameters of the response function, the iii smoothness of the blurring function, the long memory parameters of the errors, and how the total number of observations is distributed among the channels.

De nombreuses applications, en vision par ordinateur ou en médecine notamment,ont pour but d'identifier des similarités entre plusieurs images ou signaux. On peut alors détecter des objets, les suivre, ou recouper des prises de vue. Dans tous les cas, les procédures algorithmiques qui traitent les images utilisent une sélection de points-clefs qu'elles essayent ensuite de mettre en correspondance par paire. Elles calculent pour chaque point un descripteur qui le caractérise, le discrimine des autres. Parmi toutes les procédures possibles,la plus utilisée aujourd'hui est SIFT, qui sélectionne les points-clefs, calcule des descripteurs et propose un critère de mise en correspondance globale. Dans une première partie, nous tentons d'améliorer cet algorithme en changeant le descripteur original qui nécessite de trouver l'argument du maximum d'un histogramme : en effet, son calcul est statistiquement instable. Nous devons alors également changer le critère de mise en correspondance de deux descripteurs. Il en résulte un problème de test non paramétrique dans lequel à la fois l'hypothèse nulle et alternative sont composites, et même non paramétriques. Nous utilisons le test du rapport de vraisemblance généralisé afin d'exhiber des procédures de test consistantes, et proposons une étude minimax du problème. Dans une seconde partie, nous nous intéressons à l'optimalité d'une procédure globale de mise en correspondance. Nous énonçons un modèle statistique dans lequel des descripteurs sont présents dans un certain ordre dans une première image, et dans un autre dans une seconde image. La mise en correspondance revient alors à l'estimation d'une permutation. Nous donnons un critère d'optimalité au sens minimax pour les estimateurs. Nous utilisons en particulier la vraisemblance afin de trouver plusieurs estimateurs consistants, et même optimaux sous certaines conditions. Enfin, nous nous sommes intéressés à des aspects pratiques en montrant que nos estimateurs étaient calculables en temps raisonnable, ce qui nous a permis ensuite d'illustrer la hiérarchie de nos estimateurs par des simulations