The main claim of this paper is that the minimalist framework and optimality theory adopt more or less the same architecture of grammar: both assume that a generator defines a set S of potentially well-formed expressions that can be generated on the basis of a given input, and that there is an evaluator that selects the expressions from S that are actually grammatical in a given language L. The paper therefore proposes a model of grammar in which the strengths of the two frameworks are combined: more specifically, it is argued that the computational system of human language CHL from MP creates a set S of potentially well-formed expressions, and that these are subsequently evaluated in an optimality theoretic fashion.

In dieser Dissertation schlage ich eine Synthese (Distributed Optimality, DO) von Optimalitätstheorie und einem derivationellen, morphologischem Asatz, Distributed Morphology (DM; Halle & Marantz, 1993) vor. Durch die Integration von OT in DM wird es möglich, Phänomene, die in DM durch sprachspezifische Regeln oder Merkmale von lexikalischen Einträge erfasst werden, auf die Interaktion von verletzbaren, universellen Constraints zurückzuführen. Andererseits leistet auch DM zwei substantielle Beiträge zu DO, Lokalität und Impoverishment. Lokalität erlaubt eine formal einfache Interpretation von DO, während sich Impoverishment als unverzichtbar erweist, um Kongruenz-Morphologie adäquat zu beschreiben. Die empirische Grundlage der Arbeit sind die komplexen Kongruenzsysteme von genetisch unterschiedlichen Sprachen.<br /> Der theoretische Schwerpunkt liegt in zwei Bereichen: Erstens, sogenannte Direkt/Invers-Markierung, für die gezeigt wird, dass eine Behandlung durch Constraints über Merkmalsrealisierung am angemessensten ist. Zweitens, die Effekte von Abfolge-Constraints, die den Satus von Affixen als Präfixe und Suffixe sowie ihre relative Reihenfolge regeln. Eine konkrete Typologie für die Abfolge von Kongruenz-Affixen auf der Basis von OT-Constraints wird vorgeschlagen. / In this thesis I propose a synthesis (Distributed Optimality, DO) between Optimality Theory (OT, Prince & Smolensky, 1993) and a morphological framework in a genuine derivational tradition, namely Distributed Morphology (DM) as developed by Halle & Marantz (1993). By carrying over the apparatus of OT to DM, phenomena which are captured in DM by language-specific rules or features of lexical entries, are given a more principled account in the terms of ranked universal constraints. On the other hand, also the DM part makes two contributions, namely strong locality and impoverishment. The first gives rise to a simple formal interpretation of DO, while the latter is shown to be indispensable in any theoretically satisfying account of agreement morphology. The empirical basis of the work is given by the complex agreement morphology of genetically different languages. <br /> Theoretical focus is mainly on two areas: First, so-called direction marking which is shown to be preferably treated in terms of constraints on feature realization. Second, the effects of precedence constraints which are claimed to regulate the status of agreement affixes as prefixes or suffixes and their respective order. A universal typology for the order of agreement categories by means of OT-constraints is proposed.

All animals are adapted to the environmental conditions of the habitat they chose to live in. It was the aim of this PhD-project, to show which behavioral strategies are expressed as mechanisms to cope with the constraints, which contribute to the natural selection pressure acting on individuals. For this purpose, small mammals were exposed to different levels and types of predation risk while actively foraging. Individuals were either exposed to different predator types (airborne or ground) or combinations of both, or to indirect predators (nest predators). Risk was assumed to be distributed homogeneously, so changing the habitat or temporal adaptations where not regarded as potential options. Results show that wild-caught voles have strategic answers to this homogeneously distributed risk, which is perceived by tactile, olfactory or acoustic cues. Thus, they do not have to know an absolut quality (e.g., in terms of food provisioning and risk levels of all possible habitats), but they can adapt their behavior to the actual circumstances. Deriving risk uniform levels from cues and adjusting activity levels to the perceived risk is an option to deal with predators of the same size or with unforeseeable attack rates. Experiments showed that as long as there are no safe places or times, it is best to reduce activity and behave as inconspicuous as possible as long as the costs of missed opportunities do not exceed the benefits of a higher survival probability. Test showed that these costs apparently grow faster for males than for females, especially in times of inactivity. This is supported by strong predatory pressure on the most active groups of rodents (young males, sexually active or dispersers) leading to extremely female-biased operative sex ratios in natural populations. Other groups of animals, those with parental duties such as nest guarding, for example, have to deal with the actual risk in their habitat as well. Strategies to indirect predation pressure were tested by using bank vole mothers, confronted with a nest predator that posed no actual threat to themselves but to their young (Sorex araneus). They reduced travelling and concentrated their effort in the presence of shrews, independent of the different nutritional provisioning of food by varying resource levels due to the different seasons. Additionally, they exhibited nest-guarding strategies by not foraging in the vicinity of the nest site in order to reduce conspicuous scent marks. The repetition of the experiment in summer and autumn showed that changing environmental constraints can have a severe impact on results of outdoor studies. In our case, changing resource levels changed the type of interaction between the two species. The experiments show that it is important to analyze decision making and optimality models on an individual level, and, when that is not possible (maybe because of the constraints of field work), groups of animals should be classified by using the least common denominator that can be identified (such as sex, age, origin or kinship). This will control for the effects of the sex or stage of life history or the individual´s reproductive and nutritional status on decision making and will narrow the wide behavioral variability associated with the complex term of optimality. / Das Verhalten von Tieren ist das Ergebnis eines kontinuierlichen Anpassungsprozesses im Laufe der Evolution einer Art und damit der Veränderung der Umgebung in der es lebt und der Interaktion mit anderen Arten. Dies wird besonders deutlich im Verhalten von potentiellen Beutetieren, ihre Strategien beinhalten meist ein möglichst unauffälliges Verhalten im Zusammenspiel mit reduzierter Bewegung und möglichst guter Tarnung. Dementgegen stehen essentielle Bedürfnisse, wie zum Beispiel die Nahrungssuche, die Verteidigung von Ressourcen (zum Beispiel Territorien, Futterstellen) und die Suche nach Paarungspartnern. Beutetiere leben also in einem Spannungsfeld indem sie Ihr Verhalten optimieren müssen. Hierbei stehen die Ernährung, erfolgreiche Verpaarung und andere Chancen auf der einen Seite, die Vermeidung von Begegnungen mit Prädatoren auf der anderen. Vor allem Kleinsäuger sind häufig als Beutetiere mit einer Vielzahl von Prädatoren aus der Luft und auf dem Boden konfrontiert. Sie müssen für die verschiedenen Bedrohungen adaptive Verhaltensanpassungen bereit haben und in der Lage sein, auf die optischen, olfaktorischen oder akustischen Signale, die die Gefahr durch Prädatoren anzeigen, mit plastischen Verhaltensmustern zu reagieren. Die vorliegende Dissertation beschäftigt sich mit bisher als Konstanten behandelten Faktoren und untersucht anhand von Verhaltensexperimenten mit wilden Wühlmäusen (Microtus arvalis) folgende Fragestellungen: - Wie verhalten sich Tiere, die einer homogenen Risikoverteilung ausgesetzt sind, zum Beispiel weil ihr Prädator genauso gross ist wie sie, im gleichen Habitat lebt und es keinen sicheren Ort gibt? - Mit welchen Anpassungen reagieren Tiere, wenn sie gleichzeitig verschiedenen Prädatoren ausgesetzt sind? - Wie unterscheiden sich die Nahrungssuchstrategien von Männchen und Weibchen? - Wie verhalten sich laktierende Weibchen, die einer permanenten, indirekten Gefahr, z.B. durch einen Nestprädator ausgesetzt sind? Die Ergebnisse der verschiedenen Versuche in künstlichen Arenen und Aussengehegen zeigen, dass die Mäuse in der Lage sind, adaptive Verhaltensanpassung an homogenes Risiko und verschiedene Prädationstypen abzurufen. So sind sie in der Lage, Luft- von Bodenprädatoren zu unterscheiden und jeweils das Verhalten zu zeigen, dass die größtmögliche Sicherheit mit sich bringt. Die simultane Kombination von verschiedenen Prädatoren bewirkt hierbei additive Effekte. Gibt es keine Auswahl zwischen Habitaten, sondern nur unterschiedliche homogene Risikolevel, reagieren sie auf steigendes Risiko immer mit verminderter Aktivität und konzentrieren ihre Nahrungssuche auf weniger Futterstellen, beuten diese dafür jedoch länger aus. Die Wertigkeit von Futterstellen und alternativen Optionen verändert sich also mit dem Risikolevel. Ähnliches zeigt sich auch in den unterschiedlichen Futtersuchstrategien von Männchen und Weibchen. Die untersuchte Art ist polygyn und multivoltin, dementsprechend verbinden die Männchen mit ihrer Nahrungssuche Aktivitäten wie die Suche nach Paarungspartnern und unterscheiden sich die Aktivitätsmuster zwischen Männchen und Weibchen. Zusätzlich zeigen die Ergebnisse, das laktierende Weibchen in der Lage sind, das Risiko für sich und für Ihre Jungen abzuschätzen, wenn sie mit einem Nestprädator (Sorex araneus) konfrontiert werden. Für die Interaktion zwischen diesen beiden Arten ist jedoch die Saison (und damit die Ressourcenlage), in der sie sich begegnen, von entscheidender Bedeutung. Wühlmäuse reagieren mit entsprechenden Verhaltensanpassungen zum Schutz des Nestes um die Überlebenschancen ihrer letzten Würfe im Herbst zu erhöhen. Die vorliegende Arbeit konnte grundsätzliche Probleme der antiprädatorischen Verhaltensanpassung von Beutetieren klären und wichtige Faktoren der Entscheidungsfindung unter Prädationsdruck analysieren. Sie zeigt, dass Tiere das Risiko in ihrer Umgebung nicht unbedingt über direkt Signale wahrnehmen, sondern ihre Verhaltensstrategien einem empfundenen Gesamtrisikolevel anpassen. Dies ermöglicht ihnen, adaptive Strategien zu verfolgen, auch wenn sie keine Auswahl an sicheren Habitaten haben. Sie zeigt auch die unterschiedliche Wahrnehmung von Risiken durch Männchen und Weibchen, die durch die unterschiedlichen mit der Aktivität zusätzlich wahrgenommenen Chancen verknüpft zu sein scheint. Zusätzlich wurde der Einfluss des reproduktiven Status (z.B. laktierend), sowie der Ressourcenlage (z. B. je nach Saison) nachgewiesen.

This thesis consists of three chapters. The first chapter focuses on adaptive smoothing splines for fitting functions with varying roughness. In the first part of the first chapter, we study an asymptotically optimal procedure to choose the value of a discretized version of the variable smoothing parameter in adaptive smoothing splines. With the choice given by the multivariate version of the generalized cross validation, the resulting adaptive smoothing spline estimator is shown to be consistent and asymptotically optimal under some general conditions. In the second part, we derive the asymptotically optimal local penalty function, which is subsequently used for the derivation of the locally optimal smoothing spline estimator. In the second chapter, we propose a Lipschitz regularity based statistical model, and apply it to coordinate measuring machine (CMM) data to estimate the form error of a manufactured product and to determine the optimal sampling positions of CMM measurements. Our proposed wavelet-based model takes advantage of the fact that the Lipschitz regularity holds for the CMM data. The third chapter focuses on the classification of functional data which are known to be well separable within a particular interval. We propose an interval based classifier. We first estimate a baseline of each class via convex optimization, and then identify an optimal interval that maximizes the difference among the baselines. Our interval based classifier is constructed based on the identified optimal interval. The derived classifier can be implemented via a low-order-of-complexity algorithm.

In a generic wireless network where the activation of a transmission link is subject to its signal-to-noise-and-interference ratio (SINR) constraint, one of the most fundamental and yet challenging problem is to find the maximum number of simultaneous transmissions. In this thesis, we consider and study in detail the problem of maximum link activation in wireless networks based on the SINR model. Integer Linear Programming has been used as the main tool in this thesis for the design of algorithms. Fast algorithms have been proposed for the delivery of near-optimal results time-efficiently. With the state-of-art Gurobi optimization solver, both the conventional approach consisting of all the SINR constraints explicitly and the exact algorithm developed recently using cutting planes have been implemented in the thesis. Based on those implementations, new solution algorithms have been proposed for the fast delivery of solutions. Instead of considering interference from all other links, an interference range has been proposed. Two scenarios have been considered, namely the optimistic case and the pessimistic case. The optimistic case considers no interference from outside the interference range, while the pessimistic case considers the interference from outside the range as a common large value. Together with the algorithms, further enhancement procedures on the data analysis have also been proposed to facilitate the computation in the solver.

An analytical framework is developed for distributed management of large networks where each node makes locally its decisions. Two issues remain open. One is whether a distributed algorithm would result in a near-optimal management. The other is the complexity, i.e., whether a distributed algorithm would scale gracefully with a network size. We study these issues through modeling, approximation, and randomized distributed algorithms. For near-optimality issue, we first derive a global probabilistic model of network management variables which characterizes the complex spatial dependence of the variables. The spatial dependence results from externally imposed management constraints and internal properties of communication environments. We then apply probabilistic graphical models in machine learning to show when and whether the global model can be approximated by a local model. This study results in a sufficient condition for distributed management to be nearly optimal. We then show how to obtain a near-optimal configuration through decentralized adaptation of local configurations. We next derive a near-optimal distributed inference algorithm based on the derived local model. We characterize the trade-off between near-optimality and complexity of distributed and statistical management. We validate our formulation and theory through simulations.

Recently, various approximate design problems for low-degree trigonometric regression models on a partial circle have been solved. In this paper we consider approximate and exact optimal design problems for first-order trigonometric regression models without intercept on a partial circle. We investigate the intricate geometry of the non-convex exact trigonometric moment set and provide characterizations of its boundary. Building on these results we obtain a complete solution of the exact D-optimal design problem. It is shown that the structure of the optimal designs depends on both the length of the design interval and the number of observations.

In this work minimally supported D-optimal designs for response surface models with spatially correlated errors are studied. The spatially correlated errors describe the correlation between two measurements depending on their distance d through the covariance function C(d)=exp(-rd). In one dimensional design space, the minimally supported D-optimal designs for polynomial models with spatially correlated errors include two end points and are symmetric to the center of the design region. Exact solutions for simple linear and quadratic regression models are presented. For models with third or higher order, numerical solutions are given. While in two dimensional design space, the minimally supported D-optimal designs are invariant under translation¡Brotation and reflection. Numerical results show that a regular triangle on the experimental region of a circle is a minimally supported D-optimal design for the first-order response surface model.

We consider the constrained convex minimization problem: min_x∈C f(x) we will present gradient projection method which generates a sequence x^k according to the formula x^(k+1) = P_c(x^k − £\_k∇f(x^k)), k= 0, 1, ¡P ¡P ¡P , our ideal is rewritten the formula as a xed point algorithm: x^(k+1) = T_(£\k)x^k, k = 0, 1, ¡P ¡P ¡P is used to solve the minimization problem. In this paper, we present the gradient projection method(GPM) and different choices of the stepsize to discuss the convergence of gradient projection method which converge to a solution of the concerned problem.

In this dissertation, we study the single machine scheduling problem with an objective of minimizing the total completion time subject to release dates. The problem, denoted 1|rj £UCj ,was known to be strongly NP-hard and both theoretically and practically important. The focus of the research in this dissertation is to develop the efficient algorithms for solving the 1|rj|£UCj problem. This thesis contains two parts. In the first part, the theme concerns the approximation approach. We derive a necessary and sufficient condition for local optimality, which can be implemented as a priority rule and be used to construct three heuristic algorithms with running times of O(n log n). By ¡¨local optimality¡¨, we mean the optimality of all candidates whenever a job is selected in a schedule, without considering the other jobs preceding or following. This is the most broadly considered concepts of locally optimal rule. We also identify a dominant subset which is strictly contained in each of all known dominant subsets, where a dominant subset is a set of solutions containing all optimal schedules. In the second part, we develop our optimality algorithms for the 1|rj |£UCj problem. First, we present a lemma for estimating the sum of delay times of the rest jobs, if the starting time is delayed a period of time in a schedule. Then, using the lemma, partially, we proceed to develop a new partition property and three dominance theorems, that will be used and have improved the branch-and-bound algorithms for our optimization approach. By exploiting the insights gained from our heuristics as a branching scheme and by exploiting our heuristics as an upper bounding procedure, we propose three branch-and-bound algorithms. Our algorithms can optimally solve the problem up to 120 jobs, which is known to be the best till now.