Routing messages between pairs of nodes is one of the most fundamental tasks in any distributed computing system. An Interval Routing Scheme (IRS) is a well-known, space-efficient routing strategy for routing messages in a network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link l at a node v indicates the set of destination addresses of the messages which should be forwarded through l at v. When studying interval routing schemes, there are two main problems to be considered: a) Which classes of networks do support a specific routing scheme? b) Assuming that a given network supports IRS, how good are the paths traversed by messages? The first problem is known as the characterization problem and has been studied for several types of IRS. In this thesis, we study the characterization problem for various schemes in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS) and the label assigned to each link of the network is a list of d 1-dimensional intervals. This is known as Multi-dimensional IRS (MIRS) and is an extension of the the original IRS. We completely characterize the class of network which support MIRS for linear (which has no cyclic intervals) and strict (which has no intervals assigned to a link at a node v containing the label of v) MIRS. In real networks usually the costs of links may vary over time (dynamic cost links). We also give a complete characterization for the class of networks which support a certain type of MIRS which routes all messages on shortest paths in a network with dynamic cost links. The main criterion used to measure the quality of routing (the second problem) is the length of routing paths. In this thesis we also investigate this problem for MIRS and prove two lower bounds on the length of the longest routing path. These are the only known general results for MIRS. Finally, we study the relationship between various types of MIRS and the problem of drawing a hypergraph. Using some of our results we prove a tight bound on the number of dimensions of the space needed to draw a hypergraph.

The main goal of this thesis is to investigate the complexity of a variety of problems related to text indexing and text searching. We present new data structures that can be used as building blocks for full-text indices which occupies minute space (FM-indexes) and wavelet trees. These data structures also can be used to represent labeled trees and posting lists. Labeled trees are applied in XML documents, and posting lists in search engines. The main emphasis of this thesis is on lower bounds for time-space tradeoffs for the following problems: the rank/select problem, the problem of representing a string of balanced parentheses, the text retrieval problem, the problem of computing a permutation and its inverse, and the problem of representing a binary relation. These results are divided in two groups: lower bounds in the cell probe model and lower bounds in the indexing model. The cell probe model is the most natural and widely accepted framework for studying data structures. In this model, we are concerned with the total space used by a data structure and the total number of accesses (probes) it performs to memory, while computation is free of charge. The indexing model imposes an additional restriction on the storage: the object in question must be stored in its raw form together with a small index that facilitates an efficient implementation of a given set of queries, e.g. finding rank, select, matching parenthesis, or an occurrence of a given pattern in a given text (for the text retrieval problem). We propose a new technique for proving lower bounds in the indexing model and use it to obtain lower bounds for the rank/select problem and the balanced parentheses problem. We also improve the existing techniques of Demaine and Lopez-Ortiz using compression and present stronger lower bounds for the text retrieval problem in the indexing model. The most important result of this thesis is a new technique for cell probe lower bounds. We demonstrate its strength by proving new lower bounds for the problem of representing permutations, the text retrieval problem, and the problem of representing binary relations. (Previously, there were no non-trivial results known for these problems.) In addition, we note that the lower bounds for the permutations problem and the binary relations problem are tight for a wide range of parameters, e.g. the running time of queries, the size and density of the relation.

In this thesis, we study different Internet pricing schemes and how they can be applied to a multiple ISP environment. We first take a look at the current Internet architecture. Then the different classes that make up the Internet hierarchy are discussed. We also take a look at peering among Internet Service Providers (ISPs) and when it is a good idea for an ISP to consider peering. Moreover, advantages and disadvantages of peering are discussed along with speculations of the evolution of the Internet peering ecosystem. We then consider different pricing schemes that have been proposed and study the factors that make up a good pricing plan. Finally, we apply some game theoretical concepts to discuss how different ISPs could interact together. We choose a pricing model based on a Stackelberg game that takes into consideration the effect of the traffic variation among different customers in a multiple ISP environment. It allows customers to specify their desired QoS in terms of maximum allowable end-to-end delay. Customers only pay for the portion of traffic that meet this delay bound. Moreover, we show the effectiveness of adopting this model through a comparison with a model that does not take traffic variation into account. We also develop a naïve case and compare it to our more sophisticated approach.

An important element of successful engineering design is the effective management of resources to support design decisions. Design decisions can be thought of as having two phasesa formulation phase and a solution phase. As part of the formulation phase, engineers must decide how much information to collect and which models to use to support the design decision. Since more information and more accurate models come at a greater cost, a cost-benefit trade-off must be made. Previous work has considered such trade-offs in decision problems when all aspects of the decision problem can be represented using precise probabilities, an assumption that is not justified when information is sparse. In this thesis, we use imprecise probabilities to manage the information cost-benefit trade-off for two decision problems in which the quality of the information is imprecise: 1) The decision of when to stop collecting statistical data about a quantity that is characterized by a probability distribution with unknown parameters; and 2) The selection of the most preferred model to help guide a particular design decision when the model accuracy is characterized as an interval. For each case, a separate novel approach is developed in which the principles of information economics are incorporated into the information management decision. The problem of statistical data collection is explored with a pressure vessel design. This design problem requires the characterization of the probability distribution that describes a novel material's strength. The model selection approach is explored with the design of an I-beam structure. The designer must decide how accurate of a model to use to predict the maximum deflection in the span of the structure. For both problems, it is concluded that the information economic approach developed in this thesis can assist engineers in their information management decisions.

We consider the problem of scheduling a given set of tasks on multiple pro- cessors with predefined periods of unavailability, with the aim of minimizing the maximum completion time. Since this problem is strongly NP-hard, polynomial ap- proximation algorithms are being studied for its solution. Among these, the best known are LPT (largest processing time first) and Multifit with their variants. We give a Multifit-based algorithm, FFDL Multifit, which has an optimal worst- case performance in the class of polynomial algorithms for same-speed processors with at most two downtimes on each machine, and for uniform processors with at most one downtime on each machine, assuming that P 6= NP. Our algorithm finishes within 3/2 the maximum between the end of the last downtime and the end of the optimal schedule. This bound is asymptotically tight in the class of polynomial algorithms assuming that P 6= NP. For same-speed processors with at most k downtimes on each machine our algorithm finishes within ( 3 2 + 1 2k ) the end of the last downtime or the end of the optimal schedule. For problems where the optimal schedule ends after the last downtime, and when the downtimes represent fixed jobs, the maximum completion time of FFDL Multifit is within 3 2 or ( 3 2+ 1 2k ) of the optimal maximum completion time. We also give an LPT-based algorithm, LPTX, which matches the performance of FFDL Multifit for same-speed processors with at most one downtime on each machine, and is thus optimal in the class of polynomial algorithms for this case. LPTX differs from LPT in that it uses a specific order of processors to assign tasks if two processors become available at the same time. For a similar problem, when there is at most one downtime on each machine and no more than half of the machines are shut down at the same time, we show that a bound of 2 obtained in a previous work for LPT is asymptotically tight in the class of polynomial algorithms assuming that P 6= NP.

This study investigates the Fisher Effect for a sample of ten developed countries and ten developing countries. The study examines whether the nominal interest rate adjusts to the expected inflation rate in the long run. The distinction between the developed countries and developing countries also enables to identify special conditions under which Fisher Effect is more likely to hold. To analyze the long run relationship between the nominal interest rate and expected inflation rate, Bounds test approach of Pesaran et. al. (2001) is utilized. Estimation results show that the adjustment of nominal interest rate to expected inflation is encountered mostly for the developing countries which have inflationary history in their economies.

In this thesis, mechanical and elastic behaviour of anisotropic materials are inves- tigated in order to understand the optimum mechanical behaviour of them in selected directions. For an anisotropic material with known elastic constants, it is possible to choose the best set of e&curren / ective elastic constants and e&curren / ective eigen- values which determine the optimum mechanical and elastic properties of it and also represent the material in a speci.ed greater material symmetry. For this reason, bounds on the e&curren / ective elastic constants which are the best set of elastic constants and e&curren / ective eigenvalues of materials have been constructed symbollicaly for all anisotropic elastic symmetries by using Hill [4,13] approach. Anisotropic Hooke.s law and its Kelvin inspired formulation are described and generalized Hill inequalities are explained in detail. For di&curren / erent types of sym- metries, materials were selected randomly and data of elastic constants for them were collected. These data have been used to calculate bounds on the e&curren / ective elastic constants and e&curren / ective eigenvalues. Finally, by examining numerical results of bounds given in tables, it is seen that the materials selected from the same symmetry type which have larger interval between the bounds, are more anisotropic, whereas some materials which have smaller interval between the bounds, are closer to isotropy.

This study analyzes the J-curve effect for Turkey&rsquo / s bilateral trade with her three main trading partners / Germany, USA and Italy, for consumption, capital and intermediate goods. The bounds test is used to test for cointegration among the trade balance, the real bilateral exchange rate, the real domestic income and the real foreign income. The results show that the real exchange rate is not a significant determinant of trade in the short run. In the long run, it is significant only for trade with USA in consumption goods. Moreover, J-curve does not exist for Turkey&rsquo / s bilateral trade with Germany, USA, and Italy in consumption, capital and intermediate goods. The results support existence of a link between the bilateral trade balances and the real domestic income both in the short run and the long run.

This study analyzes the effect of capital outflows on economic growth though the channels described in sudden stop literature. Using the autoregressive distributed lag (ARDL) bounds testing approach / it is found that there is a cointegration between capital inflows, real exchange rate and real GDP. The results show that there is a significant positive long-run relation between capital inflows and growth. It is also found that capital inflows affect real output in the short run. The results show that real exchange rate is not a significant determinant of real output both in the short run and long run. Moreover, in order to capture the dynamic responses, a vector autoregressive (VAR) methodology has been employed. The results show that a negative innovation in capital inflows causes real exchange rate depreciation and output contraction.

In this thesis we collect the study of two problems in the Calculus of Variations and Partial Differential Equations. Our first group of results concern the analysis of minimizers in a variational model describing the shape of liquid drops and crystals under the influence of gravity, resting on a horizontal surface. Making use of anisotropic symmetrization techniques and an analysis of fine properties of minimizers within the class of sets of finite perimeter, we establish existence, convexity and symmetry of minimizers. In the case of smooth surface tensions, we obtain uniqueness of minimizers via an ODE characterization. In the second group of results discussed in this thesis, which is joint work with A. Vasseur, we treat a problem in compressible fluid dynamics, establishing a uniform bound from below on the temperature for a variant of the compressible Navier-Stokes-Fourier system under suitable hypotheses. This system of equations forms a mathematical model of the motion of a compressible fluid subject to heat conduction. Building upon the work of (Mellet, Vasseur 2009), we identify a class of weak solutions satisfying a localized form of the entropy inequality (adapted to measure the set where the temperature becomes small) and use a form of the De Giorgi argument for L[superscript infinity] bounds of solutions to elliptic equations with bounded measurable coefficients. / text