In der Dissertation werden Aufgaben der Zwei-Ebenen-Optimierung mit diskreter unterer und stetiger oberer Ebene betrachtet. Es werden die Struktur dieser Aufgaben analysiert und Optimalitätsbedingungen angegeben. Dies erfolgt sowohl für den optimistischen und den pessimistischen Lösungszugang als auch für einen Lösungszugang mittels Auswahlfunktionen. Anschließend werden die theoretischen Ergebnisse auf drei verschiedene Aufgabenklassen angewendet.

Knotenfärbungen mit Abstandsbedingungen sind graphentheoretische Konzepte, motiviert durch das praktische Problem der Frequenzzuweisung in Mobilfunknetzen. In der Arbeit werden verschiedene Varianten solcher Färbungen vorgestellt. Für (Listen-)Färbungen mit einer beliebigen Anzahl r von Abstandsbedingungen werden allgemeine Eigenschaften und Schranken für die benötigte Anzahl von Farben bewiesen. Anschließend wird der Spezialfall r=2 behandelt. Färbungen mit zwei Abstandsbedingungen - die sogenannten L(d,s)-Labellings - werden für eine Reihe von Graphenklassen untersucht, u.a. für reguläre Parkettierungen, Weg- und Kreispotenzen und Graphen mit Durchmesser 2. Die Listenversion dieser Färbungen - die sogenannten L(d,s)-List Labellings - werden für Wege, Sterne, Kreise und Kakteen betrachtet. Ferner werden Untersuchungen zum Zusammenhang von L(2,1)-Labellings und L(2,1)-List Labellings bei speziellen Bäumen durchgeführt.

The traveling salesperson or salesman problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. In addition to vehicle routing, many other applications, e.g., computer wiring, cutting wallpaper, job sequencing or several data visualization techniques, require the solution of a TSP. In this paper we introduce the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem. The package features S3 classes for specifying a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. In addition, it provides an interface to Concorde, one of the best exact TSP solvers currently available. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Quels peuvent être les espaces d’interaction entre écriture et écologie – comprises toutes deux dans leur sens large – à l’ère de l’Anthropocène ? En prenant pour pivot de réflexion les textes de Wu Ming-yi吳明益 (1971-), auteur taïwanais contemporain, cette thèse souhaite interroger ces interactions à travers trois modalités :1) la mise en narration de l’environnement naturel : que signifie « écrire la nature » ? Quelles incidences esthétiques, politiques, ontologiques induisent l’utilisation de la catégorie discursive de « nature » et son dépassement, à travers par exemple l’écriture de l’espace urbain, au profit d’une « écopoétique » ?2) l’écriture et la pratique écologiste : comment l’écriture investit les plateformes idéologiques, de la réécriture de l’histoire (post)coloniale de Taïwan à la résistance militante ?3) l’écriture et l’imagination littéraire de devenirs-humain et de devenirs-monde alternatifs : comment l’écriture peut fait naître la possibilité d’envisager l’existence d’un monde commun respectueux du divers ?À l’appui d’une lecture écocritique des œuvres de Wu Ming-yi – sans limitation de genre (romans, nouvelles, essais et même travaux académiques) – et leur mise en perspective avec d’autres textes (littéraires ou non) et issus d’horizons géographiques différents, l’objectif de cette thèse est ainsi de réfléchir sur la poétique de la relation telle qu’elle s’exprime dans l’appropriation par Wu de problématiques environnementales dans le contexte spécifique de Taïwan.Nous essaierons de nous intéresser plus particulièrement à l’écopoétique en tant que réflexion sur l’idée de « nature », en tant que programme cosmopolitique et en tant que philosophie concrète et rhizomatique de la Relation. / Due to its highly transversal dimension, the contemporary paradigm of the Anthropocene forces us to profoundly rethink the mapping of knowledge domains. Then, how to reconsider the interstitial spaces between ecology and writing, at an age when the human influence has become the most powerful geophysical force on the planet? By focusing mainly on the Taiwanese contemporary writer Wu Ming-yi 吳明益 (1971-), this thesis addresses these interactions through three lenses: 1) writing and observation of the natural environment; 2) writing and environmental 2 activism and 3) writing and the literary imagination of alternative relational becomings. This thesis offers an ecocritical reading of Wu Ming-yi’s works putting them into perspective with other texts (literary or not) coming from different geographical backgrounds. This study aims at highlighting the way in which Wu’s texts are creating a kind of poetics of Relation in the socio-historical context of Taiwan, in a time when ecological crisis transcend our normative conceptions of the local and the global.

La présente thèse examine l’apparition d’un sujet de l’écriture chinoise durant la période allant de la première guerre de l’opium à la troisième guerre d’Indochine. « Écriture » est ici comprise, d’une part, au sens strict de l’activité littéraire et, d’autre part, au sens plus large, philosophique, que la déconstruction a donné à ce terme. Ainsi, la notion d’excription (néologisme emprunté au philosophe Jean-Luc Nancy) nous permet de revisiter un ensemble de textes qui ont mis au cœur de leur réflexion ou de leur expérience la question de la création, à travers l’écriture, d’un sujet et d’une communauté de sujets. Au cours des trois parties qui la composent, cette thèse interroge transversalement les hypothèses historiques sur la modernité de sinologues tels que Naitô Konan et Takeuchi Yoshimi, ainsi que les conduites créatrices de Huang Zunxian, Wifredo Lam ou encore Zhang Guixing. Car excription signifie aussi que la recherche menée suit un mouvement d’extériorisation, de mise au dehors du sens que peuvent recouvrir le sujet chinois et sa communauté. / This dissertation studies the birth of what we term the subject of Chinese writing, during the period that stretches from the first Opium War to the Third Indochina War. Our research understands “writing” in the narrow sense of literary activity but also in the wider sense that deconstruction has attached to it. Hence, excription as a philosophical concept (created by the philosopher Jean-Luc Nancy) allows us to reinterpret a number of texts whose central thought or experience is the creation of a subject and a community of such subjects. Throughout three parts we read transversally the historical hypotheses on modernity by sinologist such as Naito Konan and Takeuchi Yoshimi as well as the poetic creations of Huang Zunxian, Wifredo Lam or Zhang Guixing. One must indeed keep in mind that excription also means a movement of externalization of meaning, that, precisely, of the Chinese subject and his community.

Die ukrainische Sprache, die zu den Nominativ-Akkusativ-Sprachen gehört, weist sowohl historisch als auch synchron Abweichungen vom kanonischen Lizensierungsmuster dieser beiden Kasus auf. So kennt das Ukrainische resultative, inkongruente, in den Finitheitsmerkmalen neutralisierten Passiv-Partizipien auf -no, -to, die wie finite Aktiv-Verben ihrem internen Argument Akkusativ zuweisen, aber historisch auch Nominativ am Patiensargument lizensierten. Solche Kasus-Zuweisung am Patiens passivischer und impersonaler Verben bei fehlender oder Default-Kongruenz stellt einen wichtigen Prüfstein für die theoretische Erfassung von Kasus, Finitheitsmerkmale und Subjektmarkierung dar. Das Ziel der Untersuchung war, über die etymologische Fragestellung hinaus, ein korpus-basiertes und quantifizierbares Bild des diachronen grammatischen Wandels der -no, -to-Formen im Mittelukrainischen zu erstellen. Synchron sind -no, -to bereits gut erforscht: die Struktur erlaubt eine overte Agensangabe im Instrumental und eine optional eingesetzte overte Kopula. Diagnostische Subjekteigenschaften wie Kontrolle in die Infinitiv- und Partizipialkontexte, sowie die Bindung von Reflexiva greifen nicht. Historisch dagegen bestehen noch große empirische Lücken und Beschreibungsdesiderate. Es wurden einige der empirischen Lücken in der Diachronie der -no, -to auf der Grundlage eines elektronischen, diachronen (1500-1800) mittelgroßen Korpus literarischer und administrativer Texte geschlossen: die Arbeit beschäftigt sich mit der Kongruenz und Transitivität der -no, -to und untersucht sie parallel zu den morphologisch identischen passiven kongruierenden -no, -to. / The Ukrainian language belongs to the nominative-accusative languages and demonstrates both historically and synchronically the deviations from the canonical case licensing pattern. That is, Ukrainian has resultative, non-agreeing and non-finite passive participles ending in either -no or -to that assign accusative to their internal argument, just like finite active verbs do. Historically -no, -to forms licensed the nominative on the patience argument as well. Accusative case assignment on the patience in impersonal verbs that lack agreement represents an important touchstone for the theoretical understanding of case, finiteness and subject marking. Along with the etymological questions, the aim of this investigation was to obtain a corpus-based quantifiable picture of the diachronic grammatical change of -no, -to forms in Middle Ukrainian. The modern -no, -to structure has already been properly investigated: it is clear that the structure allows for an overt agent phrase in instrumental and for an optional copula. Diagnostic subject properties like control into the infinitival and participial contexts, as well as the binding of reflexives do not apply. Historically however, there are large empirical gaps and desiderata as to the development of -no, -to. The thesis closes several of the empirical gaps in the diachrony of -no, -to on the basis of a middle-sized electronic corpus of literary and administrative texts from 1500-1800. The thesis deals with the agreement and transitivity of non-agreeing -no, -to that have been investigated parallel to the morphologically identical to them agreeing passive -no, -to.

La place du mort est une étude topographique des sépultures païennes de l'âge de fer en Islande. Le but de ce travail est d'étudier la localisation des tombes et d'en déterminer le sens. Les résultats se fondent sur une révision critique de toutes les données disponibles en matière de site funéraire en Islande, et sur la fouille de chaque sépulture répertoriée. Les données obtenues permettent l'élaboration d'un modèle de localisation des tombes qui les situe a) loin des fermes, mais près des frontières et des routes, b) à proximité des fermes et à une courte distance de leur zone d'activité principale et c) au carrefour entre la route principale et l'allée menant au corps de ferme. Ces résultats ont été testés et confirmés par d'autres explorations de terrain et des fouilles récentes. La comparaison des tombes situées en a) et en b) met en évidence une différence intéressante : près des fermes, les tombes sont souvent orientées nord-sud, les sépultures sont en petit nombre et d'une variété limitée, et la population des défunts est majoritairement constituée d'hommes adultes ou âgés. Les tombes éloignées des fermes quant à elles sont le plus souvent orientées est-ouest, présentent une variété plus importante de biens funéraires, et contiennent des hommes et des femmes de tous âges. Les spécificités topographiques sont interprétées comme reflétant les différentes étapes du processus de la colonisation humaine de l'Islande, qui a eu lieu à la fin du IXe siècle : au stade initial, les sépultures sont placées près de l‘unique endroit important aux yeux des premiers colons : leur habitation. Puis la croissance de l'immigration entraîne de nouvelles règles, dont l'élaboration de frontières entre les propriétés agricoles, frontières signifiées entre autres par les cimetières qui y sont établis. Vers la fin de la colonisation, les démarcations sont nettes et convenues. Les frontières sont désinvesties et les lieux d'importance sont alors déplacés aux carrefours entre route principale et allée conduisant au nouveaux corps de ferme construits au sein d'établissements prééxistants. / The Place of the Dead. Viking Pagan Burial in Icelandic Cultural LandscapeLa place du mort is a topographical study of pagan burials from the late Iron Age in Iceland. The aim of this work is to investigate where burials are located, and explain the reason behind the choice of place. The results are based on a critical revision of all available data on known burial sites in Iceland, and a survey of each site in the field. The main results are presented as a model of burial location, which shows that graves were placed either a) away from farmhouses, on boundaries and by roads, or b) close to farms, and a short distance outside the main activity area of the farm, or c) at the crossroads between the main road and the home lane leading to the farm. These results were tested – and confirmed - by further field survey and excavation. When the details of each grave at the two extreme locations were compared, and interesting difference became apparent: At locations near farms, the graves are frequently orientated N-S, the grave-goods are in small numbers and of a limited variety, and the population are predominantly adult or old men. The graves far away from the farm, are most often oriented E-W, there is a greater number and a greater variety of gravegoods, and there are male and female graves of people of all ages.The differences between locations are explained as different stages of the process of the human colonisation of Iceland which occurred in the late 9th century : at the initial stage, burials were located near to the only significant place of the first settlers, the habitation. With growing immigration, people establish boundaries between farms by placing cemeteries there. Towards the end of the colonisation, where boundaries have been agreed upon, the most significant location shifts again, from boundaries, to the junction between the main road and the home track, leading to the farm which has been located between two already established settlements.

Ce travail se propose d’apporter une contribution à la reconstruction et à l’étude de la pensée arabe classiques développée dans le champ de l’adab. Remarquons que nous disons bien la pensée arabe classique développée dans le champ de l’adab, car nous pensons que si nous voulons connaître la manière dont la pensée arabe classique avait tenté de construire une vision éthique et esthétique, c’est dans l’espace de questionnement propre à l’adab qu’il faut la chercher. C’est dire que ce n’est ni dans la philosophie dite islamique, ni dans le système moral mis en place par l’Islam qu’il serait possible de trouver la vision éthique arabe ancienne telle qu’elle avait tenté de s’élaborer et de s’exprimer. En effet, si la pensée arabe classique avait et a encore quelque chose d’original à apporter à la pensée et à la culture universelles, ce ne serait ni à travers le système moral élaboré par la religion islamique, ni au moyen des réflexions menées par les philosophes, mais grâce aux idées développées dans le champ de l’adab. C’est en effet dans et à travers la pensée de l’adab que la culture arabe classique se présente comme étant véritablement elle-même, c’est-à-dire telle qu’elle nous parle à travers les éléments qui lui appartiennent proprement et intrinsèquement. Car si, comme il est souvent dit, la poésie constitue le Diwān des Arabes, c’est-à-dire l’archive de leurs traditions et de leurs sentiments, l’adab, lui, constitue à la fois leur sagesse, leur éthique et leur esthétique. / This work aims to contribute to the reconstruction and the study of classical Arab thought developed in the field of adab. Note that we say good classical Arabic thought developed in the field of adab, because we believe that if we want to know how the classical Arabic thought had tried to build an ethical and aesthetic vision is in space specific to the adab questions must be sought. This means that it is not in the so-called Islamic philosophy, or in the set up by Islamic moral system it would be possible to find old Arabic ethical vision as had tried to develop and express themselves. Indeed, While classical Arabic thought had and still has something original to bring to the mind and universal cultural thing would not be developed through the Islamic religion moral system, or through discussions by philosophers, but thanks to the ideas developed in the field of adab. Indeed, it is in and through the thought of the classical Arabic adab culture as truly present itself, that is to say, as it speaks to us through the elements that belong to it properly and intrinsically. For if, as is often said, poetry is the Diwān of the Arabs, that is to say, the archive of their traditions and their feelings, adab, he is both their wisdom, ethics and aesthetics.

Within such disciplines as Management Science, Information and Computer Science, Engineering, Mathematics and Operations Research, problems of cutting and packing (C&P) of concrete and abstract objects appear under various specifications (cutting problems, knapsack problems, container and vehicle loading problems, pallet loading, bin packing, assembly line balancing, capital budgeting, changing coins, etc.), although they all have essentially the same logical structure. In cutting problems, a large object must be divided into smaller pieces; in packing problems, small items must be combined to large objects. Most of these problems are NP-hard. Since the pioneer work of L.V. Kantorovich in 1939, which first appeared in the West in 1960, there has been a steadily growing number of contributions in this research area. In 1961, P. Gilmore and R. Gomory presented a linear programming relaxation of the one-dimensional cutting stock problem. The best-performing algorithms today are based on their relaxation. It was, however, more than three decades before the first `optimum? algorithms appeared in the literature and they even proved to perform better than heuristics. They were of two main kinds: enumerative algorithms working by separation of the feasible set and cutting plane algorithms which cut off infeasible solutions. For many other combinatorial problems, these two approaches have been successfully combined. In this thesis we do it for one-dimensional stock cutting and two-dimensional two-stage constrained cutting. For the two-dimensional problem, the combined scheme provides mostly better solutions than other methods, especially on large-scale instances, in little time. For the one-dimensional problem, the integration of cuts into the enumerative scheme improves the results of the latter only in exceptional cases. While the main optimization goal is to minimize material input or trim loss (waste), in a real-life cutting process there are some further criteria, e.g., the number of different cutting patterns (setups) and open stacks. Some new methods and models are proposed. Then, an approach combining both objectives will be presented, to our knowledge, for the first time. We believe this approach will be highly relevant for industry.

Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs. (authors' abstract) / Series: Research Report Series / Department of Statistics and Mathematics