Online optimization in the random order model

Radke, Klaus; Rossmanith, Peter

doi:5270

Online optimization in the random order model = Online-Optimierung im Random-Order-Modell

Radke, Klaus (Author)

2014

Verantwortlichkeitsangabevorgelegt von Klaus Radke

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

UmfangVIII, 79 S.

Aachen, Techn. Hochsch., Diss., 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-11-20

Online
URN: urn:nbn:de:hbz:82-opus-52709
URL: https://publications.rwth-aachen.de/record/465392/files/5270.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Online-Algorithmus (Genormte SW) ; Matching (Genormte SW) ; Packungsproblem (Genormte SW) ; Informatik (frei) ; Random-Order Modell (frei) ; Sekretärinnenproblem (frei) ; kombinatorische Auktionen (frei) ; online optimization (frei) ; random-order model (frei) ; secretary problem (frei) ; matching (frei) ; combinatorial auctions (frei) ; generalized assignment problem (frei) ; packing linear programs (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Online-Probleme besitzen die Eigenschaft, dass Informationen erst nach und nach preisgegeben werden und Entscheidungen bereits gefällt werden müssen, während zukünftige Informationen noch unbekannt sind. Diese sind in vielerlei Anwendungssituationen relevant, wie zum Beispiel bei Ressourcenzuordnungsproblemen. Um die Güte eines Algorithmus für derartige Probleme zu beweisen, geht man klassischerweise davon aus, dass der Algorithmus gegen einen fiktiven böswilligen Gegner arbeitet, welcher stets die ungünstigste Eingabe liefert. Diese Annahme ist jedoch sehr pessimistisch. In den letzten Jahren wurden daher Eingabemodelle untersucht, bei denen der Gegner nur über eingeschränkte Fähigkeiten verfügt. In dieser Arbeit werden Online-Optimierungsprobleme im Random-Order-Modell betrachtet. Bei diesem Eingabemodell spezifiziert der Gegner anfangs eine Eingabeinstanz. Im Gegensatz zum klassischen Modell darf er jedoch nicht die Reihenfolge bestimmen, in welcher diese dem Algorithmus präsentiert wird. Stattdessen wird die Eingabesequenz in zufälliger Reihenfolge offengelegt. Wir untersuchen mehrere kombinatorische Verallgemeinerungen des Sekretärinnenproblems und zeigen jeweils Algorithmen mit verbesserter Kompetitivität. Sämtliche betrachteten Probleme sind Packprobleme. Dies sind im Speziellen bipartite Matchings, kombinatorische Auktionen, das Generalized-Assignment-Problem und lineare Packprogramme. Zunächst untersuchen wir das Matchingproblem auf kantengewichteten Graphen, wenn die Knoten der einen Seite online und in zufälliger Reihenfolge aufgedeckt werden. Hierfür stellen wir einen überraschend einfachen Algorithmus vor, der den klassischen Algorithmus für das Sekretärinnenproblem verallgemeinert. Da seine erwartete Güte mit der bestmöglichen Kompetitivität für das Sekretärinnenproblem übereinstimmt, ist dieser Algorithmus optimal. Zusätzlich liefert dieser Algorithmus auch das bestmögliche Resultat für das Matroid-Sekretärinnenproblem auf transversalen Matroiden. Anschließend zeigen wir verbesserte Gütegarantien für kombinatorische Auktionen, bei denen die Bieter online und in zufälliger Reihenfolge erscheinen. Dies sind Verallgemeinerungen des kantengewichteten Matching-Problems und wir betrachten verschiedene Typen von Bewertungsfunktionen. Insbesondere betrachten wir Auktionen, bei denen die Bieter an Bündeln beschränkter bzw. unbeschränkter Größe interessiert sind oder ihre Bewertungsfunktionen submodular sind. Für das Generalized-Assignment-Problem, das eine andere Verallgemeinerung des gewichteten Matching-Problems ist, stellen wir den ersten Algorithmus mit konstanter Kompetitivität vor. Dieses Resultat verbessert auch die beste bekannte Gütegarantie für das Online-Rucksackproblem. Abschließend betrachten wir Online-Packprogramme, bei denen die Variablen in zufälliger Reihenfolge offengelegt werden. Wir stellen einen Algorithmus vor, welcher auf Instanzen mit hohem Kapazitätsverhältnis die bestmögliche Güte erreicht. Bei derartigen Instanzen ist in jeder Zeile des linearen Programms die Kapazität groß gegenüber dem maximalen Matrixeintrag. Außerdem verhält sich der Algorithmus auch nahezu optimal, wenn das Kapazitätsverhältnis nur konstant beschränkt ist. Zuletzt zeigen wir, wie man, im Falle von strategisch agierenden Agenten, den Algorithmus zu einem anreizkompatiblen Mechanismus mit nahezu identischer Güte umformen kann.

In an online problem, information is revealed incrementally and decisions have to be made before the full information is known. This occurs in various applications like, for example, resource allocation or online ad assignment. To analyze the performance of algorithms for online problems, it is classically assumed that there is a malicious adversary who always provides the worst-possible input. This, however, is a very pessimistic assumption. Therefore, in recent years, a lot of research has been done to analyze input models where the power of the adversary is restricted. In this thesis, we consider online optimization problems in the random-order model. In this online model, an adversary specifies an input instance in advance but, in contrast to the classic model, he may not determine the order in which it is revealed to the algorithm. Instead, the input sequence is revealed in random order. We analyze several combinatorial generalizations of the famous secretary problem and present algorithms with improved competitive ratios for each of them. Specifically, the problems considered here are of packing type, namely, bipartite matching, combinatorial auctions, generalized assignment and packing linear programs. First, we analyze the edge-weighted bipartite matching problem where the vertices of one side arrive online in random order. For this problem, we give a surprisingly simple algorithm that generalizes the classic algorithm for the secretary problem. Since its expected competitive ratio matches the best-possible one for the secretary problem, the algorithm is optimal. The result also gives the best-possible competitive ratio for the matroid secretary problem on transversal matroids. Then, we present improved competitive ratios for combinatorial auctions with online bidders arriving in random order. They are generalizations of the weighted matching problem and we analyze various types of valuation functions. Namely, we consider auctions where the bidders are interested in bundles of bounded or unbounded cardinality or where the valuation functions are submodular. For the online generalized assignment problem, which is another generalization of the weighted matching problem, we present the first constant-competitive algorithm. This result also improves on the best known competitive ratio for the online knapsack problem. Finally, we consider online packing LPs where the variables are revealed online in random order. For these, we present an algorithm that obtains the best-possible competitive ratio on instances with high capacity ratio, i.e., where, for every row, the capacity is large compared to the maximum entry in the constraint matrix. Furthermore, this algorithm also gives close-to-optimal results when the capacity ratio is only bounded by a constant. Additionally, we show how to modify the algorithm in the presence of strategic agents to obtain a truthful mechanism with almost identical competitive ratio.

Fulltext:
PDF