Online Bin Stretching: Algorithms and Computer Lower Bounds Author: Martin Böhm Abstract: We investigate a problem in semi-online algorithm design, called Online Bin Stretching. The problem can be understood as an online repacking problem: the goal of the algorithm is to repack items of various sizes into m containers of identical size R > 1. The input items arrive one by one and the algorithm must assign an item to a container before the next item arrives. A specialty of this problem is that there is a specific guarantee made to the algorithm: the algorithm learns at the start of the input that there exists a packing of all input items into m containers of capacity 1. Our goal is to design algorithms for this problem which successfully pack the entire incoming sequence one by one while requiring the lowest container capacity R possible. In this thesis, we show several new results about Online Bin Stretching: First, we design an algorithm that is able to pack the entire input into m containers of capacity 1.5 regardless of what the vale of m will be. Second, we show a specialized algorithm for the setting of just 3 containers; this algorithm is able to pack into 3 bins of capacity 1.375. Finally, we design and implement an involved search algorithm which is able to find lower bounds for Online Bin...

The quadratic assignment problem (QAP) is known to be one of the most computationally difficult combinatorial problems. Optimally solvable instances of the QAP remain of size n ≤ 40 with heuristics used to solve instances in the range 40 ≤ n ≤ 256. In this thesis we develop a local optimization algorithm called GradSwaps (GS). GS uses the first-order Taylor approximation (FOA) to efficiently determine improving swaps in the solution. We use GS to locally optimize instances of the QAP of size 1000 ≤ n ≤ 70000 where the data matrices are given in factored form, enabling efficient computations. We give theoretical background and justification for using the FOA and bound the error inherent in the approximation. A strategy for extending GS to larger scale QAPs using blocks of indices is described in detail. Three novel large-scale applications of the QAP are developed. First, a strategy for data visualization using an extreme learning machine (ELM) where the quality of the visualization is measured in the original data space instead of the projected space. Second, a version of the traveling salesperson problem (TSP) with the squared Euclidean distance metric; this distance metric allows the factorization of the data matrix, a key component for using GS. Third, a method for generating random data with designated distribution and correlation to an accuracy surpassing traditional techniques.

Analytical performance analysis on Direction-Of-Arrival (DOA) estimation algorithms has attracted much excellent research in recent years, various statistical properties have been revealed. However, in most of these analyses, insights of the performance were masked because of the involvement of singular values and singular vectors which depend on the character of the algorithms and data structures in a complex and nonlinear manner.

We consider several combinatorial optimization problems in a geometric set- ting. The first problem we consider is the problem of clustering to minimize the sum of radii. Given a positive integer k and a set of points with interpoint distances that satisfy the definition of being a "metric", we define a ball centered at some input point and having some radius as the set of all input points that are at a distance smaller than the radius of the ball from its center. We want to cover all input points using at most k balls so that the sum of the radii of the balls chosen is minimized. We show that when the points lie in some Euclidean space and the distance measure is the standard Euclidean metric, we can find an exact solution in polynomial time under standard assumptions about the model of computation. The second problem we consider is the Network Spanner Topology Design problem. In this problem, given a set of nodes in the network, represented by points in some geometric setting - either a plane or a 1.5-D terrain, we want to compute a height assignment function h that assigns a height to a tower at every node such that the set of pairs of nodes that can form a direct link with each other under this height function forms a connected spanner. A pair of nodes can form a direct link if they are within a bounded distance B of each other and the heights of towers at the two nodes are sufficient to achieve Line-of-Sight connectivity - i.e. the straight line connecting the top of the towers lies above any obstacles. In the planar setting where the obstacles are modeled as having a certain maximum height and minimum clearance distance, we give a constant factor approximation algorithm. In the case where the points lie on a 1.5-D terrain we illustrate that it might be hard to use Computational Geometry to achieve efficient approximations. The final problem we consider is the Multiway Barrier Cut problem. Here, given a set of points in the plane and a set of unit disk sensors also in the plane such that any path in the plane between any pair of input points hits at least one of the given sensor disks we consider the problem of finding the minimum size subset of these disks that still achieves this separation. We give a constant factor approximation algorithm for this problem.

Thesis (M.S.)--University of Missouri--Rolla, 2007. / Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed December 7, 2007) Includes bibliographical references (p. 28).

Bibliographies: leaves ii & 146-150.

Dans ce travail de thèse sont étudiés des problèmes mathématiques (théorie et approximation) issus de la théorie de la dynamique des gaz compressibles et modélisés par les équations d'Euler. L'approximation numérique de ces problèmes physiques a nécessite une étude détaillée de quelques problèmes de conditions aux limites. Les approximations numériques obtenues sont basées sur la methode des volumes finis, qui nous a semble la mieux adaptée pour la discrétisation des systèmes hyperboliques de lois de conservation en général. La convergence de la methode des volumes finis est obtenue pour les problèmes de lois de conservation scalaires avec des conditions aux limites, a l'aide d'unicité dans l'espace des solutions mesures

.

En premier, nous montrons l'existence d'inégalités de Markov sur les courbes algébriques singulières de Rn. Nous donnons une signification géométrique à l'exposant de Markov en montrant qu'il est minoré par la multiplicité de la singularité de la courbe complexifiée dans Cn. Nous construisons une paramétrisation de Puiseux en la singularité réelle de la courbe complexifiée. Nous la prolongeons à un ouvert de C partout dense, afin d'obtenir la propriété d'HCP de la fonction de Green avec pôle à l'infini dans la courbe complexifiée, via la métrique des géodésiques. En second, nous montrons un théorème de type Bernstein pour les classes de fonctions intermédiaires entre les fonctions holomorphes et les fonctions indéfiniment différentiables sur des classes de compacts s-H convexes de Cn . Pour démontrer ce résultat, nous donnons une représentation intégrale sur les compacts s-H convexes de Cn des fonctions de A¥(K) via un noyau adéquat , nous approchons ce noyau par les noyaux à poids de type Henkin-Ramirez. Nous proposons une nouvelle propriété géométrique de la fonction de Green avec pôle à l'infini. Pour finir nous donnons quelques applications et corollaires.

Cette thèse est consacrée à l'étude des valeurs de la fonction zêta de Riemann aux entiers impairs. Quatre résultats sont démontrés : - Soit $a$ un nombre rationnel, $\vert a \vert <1$. Le Q-espace vectoriel engendré par $1, Li_1(a), Li_2(a),...$ est de dimension infinie. - Le Q-espace vectoriel engendré par $1, \zeta(3), \zeta(5), \zeta(7),...$ est de dimension infinie. - Il existe un entier impair $j$, $5\le j \le 169$ tel que $1, \zeta(3), \zeta(j)$ sont linéairement indépendants sur Q. - Au moins un des neuf nombres $\zeta(5), \zeta(7),..., \zeta(21)$ est irrationnel.