Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26537
Titel: Analysis of algorithms for online uni-directional conversion problems
Verfasser: Ahmad, Iftikhar
Sprache: Deutsch
Erscheinungsjahr: 2013
SWD-Schlagwörter: Online-Algorithmus
Competitive analysis
Risikomanagement
Umsetzung <Informatik>
Freie Schlagwörter: risk reward framework
theoretical analysis
experimental analysis
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: In an online uni-directional conversion problem, an online player wants to convert an asset $D$ to a desired asset $Y$. The objective of the player is to obtain the maximum amount of the desired asset. Competitive analysis is used as a tool for the design, and analysis of online algorithms for conversion problems. Although widely used, competitive analysis has its own set of drawbacks when the applicability of online algorithms in real world is considered. In this work, we investigate online uni- directional conversion problems with the objective to suggest measures for improving the applicability of online conversion algorithms in real world. First, we study competitive ratio as a coherent measure of risk and conclude that as it satisfies all the desirable axioms of coherence, competitive ratio can be used in practice. Secondly, we evaluate a selected set of online algorithms on real world as well bootstrap data to highlight the gap between theoretically guaranteed and experimentally achieved competitive ratio. The third aspect of the study deals with generating synthetic data that truly represents all possible scenarios such as market crashes. We suggest the use of Extreme Value Theory (EVT) approach. Using EVT approach, we generate synthetic data and execute a selected set of non-preemptive uni-directional online algorithms on it. The fourth contribution of the thesis includes the design and analysis of risk-aware reservation price algorithms for conversion problems. The proposed algorithms are flexible to accommodate the risk level of the online player whereas guaranteeing a bounded worst case competitive ratio as well. We evaluate our algorithms using the competitive analysis approach as well as testing the algorithms on the real world data. The results will help to improve the applicability of online conversion algorithms in real world. We conclude the work by discussing a number of open questions that will provide new directions for future research.
In einem Online-uni-directional-conversion-Problem, möchte ein Online-Spieler ein Asset $D$ in ein gewünschtes Asset $Y$ konvertieren. Das Ziel des Spielers ist es, den maximalen Wert des gewünschten Assets zu erhalten. Die competitive analysis wird als Hilfsmittel verwendet, um Online-Algorithmen für Conversion-Probleme zu entwerfen und zu analysieren. Obwohl die competitve analysis weit verbreitet ist, besitzt sie mehrere Nachteile wenn ihre Anwendbarkeit auf Online-Algorithmen in der realen Welt betrachtet wird. In dieser Arbeit werden wir online Uni-directional-conversion-Probleme betrachten, mit dem Ziel, Kennzahlen zu erarbeiten, um die Anwendbarkeit von Online-Conversion-Algorithmen in der realen Welt zu verbessern. In einem ersten Schritt untersuchen wir die competitive ratio als kohärentes Risikomaß und schließen, wenn es alle notwendigen Kohärenzaxiome erfüllt wurden, dass die competitive ratio in der Praxis eingesetzt werden kann. In einem zweiten Schritt evaluieren wir eine ausgewählte Menge an Online-Algorithmen in der realen Welt. Außerdem werden die Daten gebootstrapped, um den Unterschied zwischen der theoretisch garantierten und empirisch erreichten competitive ratio. Der dritte Aspekt dieser Arbeit betrachtet das Generieren von synthetischen Daten, welche alle möglichen Szenarien, wie beispielsweise einen Marktcrash, repräsentieren. Wir empfehlen dafür den Einsatz der Extreme-Value-Theorie (EVT). Mit der EVT generieren wir synthetische Daten und führen eine ausgewählte Menge an nicht-präemptiven Uni-directionalen-Online-Algorithmen über diesen aus. Der vierte Beitrag dieser Arbeit beinhaltet das Design und die Analyse von risk-aware Reservationspreis-Algorithmen für Conversion-Probleme. Die vorgeschlagenen Algorithmen können das Risikoniveau des Online-Spielers aufnehmen und garantieren eine begrenzte Worst-Case-Competitive-Ratio. Wir evaluieren unsere Algorithmen mit Hilfe des competitive-analysis-Ansatzes sowie dem Testen der Algorithmen auf realen Daten. Die Resultate werden in Form von Forschungsarbeiten präsentiert und helfen, die Anwendbarkeit von Online-Conversion-Algorithmen in der realen Welt zu verbessern. Wir schließen die Arbeit mit einer Diskussion über eine Reihe offener Fragen, welche neue Forschungsrichtungen für die Zukunft eröffnen.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-55226
hdl:20.500.11880/26593
http://dx.doi.org/10.22028/D291-26537
Erstgutachter: Schmidt, Günter
Tag der mündlichen Prüfung: 30-Sep-2013
SciDok-Publikation: 4-Okt-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
ia_PhD_Thesis.pdf2,68 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.