Universität zu Köln

Kloock, Markus (2003). Das Twisten von Matroiden. PhD thesis, Universität zu Köln.

Preview

PDF DTwvM.pdf Download (809kB)

Abstract

Das Twisten von Matroiden steht für das Versammeln der symmetrischen Differenzen aller Matroid-Mengen mit einer vorgegebenen Teilmenge der Grundmenge, die Matroide dabei im Kontext der Mengensysteme interpretierend. In dieser Arbeit werden die so entstehenden Mengensysteme eingehend untersucht, samt einiger Derivate und beschreibender Funktionen. Ein Schwerpunkt besteht in der Einordnung der getwisteten Matroide in ein Gefüge von bekannten Greedoid-Klassen, beschränkt hier auf Systeme, die auf ungeordneten Mengen basieren und eine Affinität zu Greedy-Algorithmen bezüglich linearer Optimierung aufweisen. Diese Beziehungen werden beschrieben und die Klassen voneinander abgegrenzt. Zusätzlich wird eine Greedoid-Eigenschaft hervorgehoben, die die Bildung einer weiteren Klasse rechtfertigen soll, mit der Begründung, dass diese Systeme, falls sie gleichzeitig Delta-Matroide sind, die lineare Optimierung einem hier dargelegten Greedy-Algorithmus anvertrauen dürfen. Dieser benötigt lediglich das gewöhnliche Mengensystem-Orakel, um in polynomiell vielen Zeitschritten, abhängig von der Größe der Grundmenge, erfolgreich zu sein. In diese Klasse gehören neben den getwisteten Matroiden auch die Matroid-Twistvereinigungen, die hier vorgestellt und diesbezüglich untersucht werden. Das Auftreten dieser Konstrukte im Rahmen des Traveling-Salesman-Problems und des verwandten Vehicle-Routing-Problems wird beschrieben. Ein Exkurs in die Polyedertheorie beinhaltet den Nachweis, dass der von Dunstan und Welsh vorgestellte verallgemeinerte Polymatroid-Algorithmus eine Charakterisierung bisubmodularer Polyeder bereitstellt. Dabei kommt der Spiegelung, als Vektorraum-Analogon zum Twisten, eine Funktion zu, die auch zu weiteren Beschreibungen für Delta-Matroide führt.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Twisting Matroids English
Translated abstract:	Abstract Language Twisting matroids means collecting the symmetric differences of all the sets in a matroid with a previously fixed subset of the ground set, thereby interpreting matroids in the context of set systems. In this thesis the set systems arising this way are extensively examined including some derivations and depicting functions. A main focus lies in the classification of twisted matroids inside a framework of well-known greedoid classes. We restrict ourselves to systems which are based on unordered sets and show some affinity to greedy algorithms regarding linear optimization. The relations are described and the classes are dissociated one from another. In addition, a special property of greedoids is stressed, which justifies the introduction of a new class, on the basis that these systems, if they are at the same time delta matroids, can leave linear optimization to a greedy algorithm. This algorithm only needs the ordinary set system oracle to succeed in polynomial many time steps, dependent on the size of the ground set. Aside from the twisted matroids, which belong to the class, this also holds for matroid twistunions, which are presented and analyzed in this respect. The occurrence of these objects within the scope of the traveling salesman problem and the related vehicle routing problem is described. An excursion into the theory of polyhedra contains the proof that the generalized polymatroid algorithm presented by Dunstan and Welsh provides a characterization of bisubmodular polyhedra. There, the concept of reflection, being the vector space analogon of twisting, plays a role that leads to further descriptions of delta matroids. English
Creators:	Creators Email ORCID ORCID Put Code Kloock, Markus Markus.Kloock@gmx.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-10319
Date:	2003
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Ehemalige Fakultäten, Institute, Seminare > Faculty of Mathematics and Natural Sciences > no entry
Subjects:	Mathematics
Uncontrolled Keywords:	Keywords Language matroid , greedoid , delta-matroid , twisten German matroid , greedoid , delta matroid , twist English
Date of oral exam:	30 November 2003
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/1031