We have investigated two greedy strategies for finding an approximation to the minimum of a convex function E, defined on a Hilbert space H. We have proved convergence rates for a modification of the orthogonal matching pursuit and its weak version under suitable conditions on the objective function E. These conditions involve the behavior of the moduli of smoothness and the modulus of uniform convexity of E.

No description available.

No description available.

No description available.

Structural motifs for the BC2N superlattices were identified from a systematic search based on a greedy algorithm. Using a tree data structure, we have retrieved seven structural models for c-BC2N 1x1x lattice which were identified previously by Sun et al. [Phys. Rev. B 64, 094108 (2001)]. Furthermore, the atomic structures with the maximum number of C-C bonds for c-BC2N 2x2x2, 3x3x3, and 4x4x4 superlattices were found by imposing the greedy algorithm in the tree data structure. This new structural motif has not been previously proposed in the literature. A total of up to 512 atoms in the c-BC2N superlattice are taken into consideration. The atoms in these superlattices are in diamond-like structural form. Furthermore, the C atoms, as well as B and N atoms, form the octahedral motif separately. The octahedral structure consisting of C is bounded with {111} facets, and each facet is interfaced to a neighboring octahedral structure consisting of B and N atoms. The electronic and mechanical properties of newly identified low energy structures were analyzed.

No description available.

This work examines a straightforward solution to a problem of satellite network resource allocation by exploring the application of an optimal algorithm to a subset of the general scheduling problem. Making some basic simplifications, such as the limitation of the mission scenarios to Low Earth Orbiting satellites, allows the effective application of the rigorous methods of the Greedy Activity-Selector algorithm. Tools such as Analytical Graphic's Satellite Tool Kit and MATLAB 5.0 are integrated to assist in the implementation of the algorithm. Several examples are presented in order to illustrate the effectiveness of the process. / Master of Science

Master of Science - Science / Axial line placement is one step in a method known as space syntax which is used in town planning to analyse architectural structures. This is becoming increasingly important in the quickly growing urban world of today. The field of axial line placement is an area of space syntax that has previously been done manually which is becoming increasingly impractical. Research is underway to automate the process and this research forms a large part of the automation. The general problem of axial line placement has been shown to be NP-complete. For this reason, previous research in this field has been focused on finding special cases where this is not the case or finding heuristics that approximate a solution. The majority of the research conducted has been on the simpler case of axial line placement in configurations of orthogonal rectangles and the only work done with convex polygons has been in the restricted case of deformed urban grids. This document presents research that finds two non-trivial special cases of convex polygons that have polynomial solutions and finds the first heuristic for general configurations of convex polygons.

Cette thèse se penche sur les problèmes de décisions devant être prises de manière séquentielle au sein d'un environnement aléatoire. Lors de chaque étape d'un tel problème décisionnel, une alternative doit être sélectionnée parmi un ensemble d'alternatives. Chaque alternative possède un gain moyen qui lui est propre et lorsque l'une d'elles est sélectionnée, celle-ci engendre un gain aléatoire. La sélection opérée peut suivre deux types d'objectifs. Dans un premier cas, les tests viseront à maximiser la somme des gains collectés. Un juste compromis doit alors être trouvé entre l'exploitation et l'exploration. Ce problème est couramment dénommé dans la littérature scientifique "multi-armed bandit problem". Dans un second cas, un nombre de sélections maximal est imposé et l'objectif consistera à répartir ces sélections de façon à augmenter les chances de trouver l'alternative présentant le gain moyen le plus élevé. Ce deuxième problème est couramment repris dans la littérature scientifique sous l'appellation "selecting the best". La sélection de type gloutonne joue un rôle important dans la résolution de ces problèmes de décision et opère en choisissant l'alternative qui s'est jusqu'ici montrée optimale. Or, la nature généralement aléatoire de l'environnement rend incertains les résultats d'une telle sélection. Dans cette thèse, nous introduisons une nouvelle quantité, appelée le "gain espéré d'une action gloutonne". Sur base de quelques propriétés de cette quantité, de nouveaux algorithmes permettant de résoudre les deux problèmes décisionnels précités seront proposés. Une attention particulière sera ici prêtée à l'application des techniques présentées au domaine de la sélection de modèles en l'apprentissage artificiel supervisé. La collaboration avec le service d'anesthésie de l'Hôpital Erasme nous a permis d'appliquer les algorithmes proposés à des données réelles, provenant du milieu médical. Nous avons également développé un système d'aide à la décision dont un prototype a déjà été testé en conditions réelles sur un échantillon restreint de patients.

One central question in theoretical computer science is how to solve problems accurately and quickly. Despite the encouraging development of various algorithmic techniques in the past, we are still at the very beginning of the understanding of these techniques. One particularly interesting paradigm is the greedy algorithm paradigm. Informally, a greedy algorithm builds a solution to a problem incrementally by making locally optimal decisions at each step. Greedy algorithms are important in algorithm design as they are natural, conceptually simple to state and usually efficient. Despite wide applications of greedy algorithms in practice, their behaviour is not well understood. However, we do know that in several specific settings, greedy algorithms can achieve good results. This thesis focuses on examining contexts in which greedy and greedy-like algorithms are successful, and extending them to more general settings. In particular, we investigate structural properties of graphs and set systems, families of special functions, and greedy approximation algorithms for several classic NP-hard problems in those contexts. A natural phenomenon we observe is a trade-off between the approximation ratio and the generality of those contexts.