Universität zu Köln

Das Twisten von Matroiden

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

[img]
Preview
PDF
Download (790Kb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Kloock, MarkusMarkus.Kloock@gmx.de
    URN: urn:nbn:de:hbz:38-10319
    Subjects: Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    matroid , greedoid , delta-matroid , twistenGerman
    matroid , greedoid , delta matroid , twistEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Keine Angabe
    Language: German
    Date: 2003
    Date Type: Completion
    Date of oral exam: 30 November 2003
    Full Text Status: Public
    Date Deposited: 12 Jan 2004 08:57:44
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/1031

    Actions (login required)

    View Item