Asymptotic Analysis of Lattice Paths and Related Structures

hackl… ist der Titel des 1. Platzes des Roland-Mittermeir-Preises 2015/2016 und wurde vom Förderverein Technische Fakultät mit EUR 1.500,–ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Benjamin Hackl, wurde der Preis im Rahmen des Festakts 10-jähriges Jubiläum der Fakultät für Technische Wissenschaften übergeben und die Arbeit wird hier kurz vorgestellt:

Zusammenfassung. Während sich die klassische Kombinatorik „nur“ mit dem Abzählen diskreter Objekte beschäftigt, interessieren wir uns im Rahmen der analytischen Kombinatorik für präzise Analysen des entsprechenden asymptotischen Verhaltens. In weniger technischen Worten sind wir also an einer möglichst genauen Charakterisierung des Wachstums von gewissen Klassen kombinatorischer Objekte interessiert. Für eine solche asymptotische Analyse werden Resultate aus einem breiten Spektrum von mathematischen Disziplinen, wie beispielsweise der klassischen Kombinatorik, der Funktionentheorie, und auch der Wahrscheinlichkeitstheorie verwendet.

Innerhalb dieser Masterarbeit spielen neben den im Titel angedeuteten Gitterpfaden auch Bäume, beides klassische diskrete Objekte mit zahllosen Anwendungen in verschiedenen na- turwissenschaftlichen und technischen Bereichen, eine zentrale Rolle. Die Arbeit ist in drei Kapitel gegliedert. In Kapitel 1, Preliminaries, geht es um die für die asymptotische Analy- se nötigen Grundlagen und Werkzeuge aus Kombinatorik (z.B. kombinatorische Klassen und erzeugende Funktionen), Funktionentheorie (Singularitätenanalyse, Mellin-Transformation), sowie Wahrscheinlichkeitstheorie (Grenzverteilungen, Martingale).

Mit Hilfe der in Kapitel 1 skizzierten Techniken geht es dann in Kapitel 2, Analysis of Lattice Paths, um die asymptotische Analyse von Gitterpfaden. Nach einer kurzen Einleitung in Ab- schnitt 2.1, in der die Terminologie geklärt wird, werden in den Abschnitten 2.2 sowie 2.3 di- verse elementare Gitterpfadklassen (Brücken, Mäander, Exkursionen) asymptotisch analysiert.

Abschnitt 2.4 bildet den Kern der Masterarbeit, in ihm werden sogenannte kulminierende Pfade untersucht. Das sind Gitterpfade mit Schritten ↗ und ↘, die auf minimaler Höhe starten und auf maximaler Höhe enden. Zu den wichtigsten Bausteinen dieser Analyse zählen die Erkenntnis, dass die wohlbekannten Chebyshev-Polynome eine zentrale Rolle spielen, sowie die asymptotische Entwicklung von Binomialkoeffizienten (2n,n−α) in einem zentralen Bereich. Neben Resultaten wie der asymptotischen Grenzverteilung und beliebig präzisen asymptotischen Entwicklungen für die Anzahl kulminierender Pfade gegebener Länge, wurde in diesem Kontext auch eine zahlentheoretische Vermutung von Zhao aus dem Jahr 2010 bewiesen.

Die Inhalte dieses Abschnittes wurden in einer geringfügig adaptierten Version 2016 in den Annals of Combinatorics publiziert.

In Kapitel 3, Analysis of Trees, liegt der Fokus schließlich auf der asymptotischen Analyse von Bäumen, wobei besonderer Wert auf das Aufzeigen der Zusammenhänge zwischen Gitterpfaden und Bäumen gelegt wird.

Zuletzt sei noch erwähnt, dass die aufwändigeren Berechnungen (insbesondere in Abschnitt 2.4) mit der Hilfe des quelloffenen Computermathematiksystems SageMath durchgeführt wurden. Der entsprechende Sourcecode findet sich in Anhang A der Arbeit. Im weiteren Umfeld der Arbeit bildete diese Implementation auch einen Teil der Motivation, ein Proposal für ein Google Summer of Code-Projekt einzureichen, welches genehmigt und erfolgreich von mir durch- geführt wurde, sodass ein Modul für asymptotische Entwicklungen mittlerweile zum Basisbestandteil von SageMath gehört.

Posted in News, Studienabgänger | Leave a comment

Local Search Heuristics for the Capacitated Vehicle Routing Problem with Structured Time Windows

truden… ist der Titel des 2. Platzes des Roland-Mittermeir-Preises 2015/2016 und wurde vom Förderverein Technische Fakultät mit EUR 1.000,–ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Christian Truden, wurde der Preis im Rahmen des Festakts 10-jähriges Jubiläum der Fakultät für Technische Wissenschaften übergeben und die Arbeit wird hier kurz vorgestellt:

Das Vehicle Routing Problem ist ein kombinatorisches Optimierungsproblem, welches ein breites Spektrum an Anwendungen im Bereich der Transportlogistik hat. Diverse Varianten kommen unter anderem bei der Planung von effizienten Liefertouren zum Einsatz. Eines der aktuell bekanntesten Anwendungsgebiete, das in der vorgelegten Arbeit im Detail betrachtet wird, findet sich im Online-Lebensmittelhandel. Hierbei wählt der Kunde auf der Website des Supermarktes ein Zeitfenster für die Zulieferung seines Einkaufes. Im Anschluss muss ein Lieferplan erstellt werden, der alle bisherigen Kundenbestellungen in ihren zugewiesenen Zeitfenstern enthält.

Das diesem Prozess zu Grunde liegende Optimierungsproblem ist das sogenannte capacitated Vehicle Routing Problem with Time Windows (cVRPTW). Es beschreibt die Herausforderung Routen ausgehend von einem Depot kosten-minimal zu planen. Die Ladekapazität der genutzten Lieferfahrzeuge und die maximale Fahrzeit der Fahrer darf hierbei nicht überschritten werden. Des weiteren muss jeder Kunde genau einmal innerhalb des ihm zugewie- senen Zeitfensters besucht werden.

Das cVRPTW gehört zur Klasse der NP-schweren Optimierungsprobleme. Für größere Probleminstanzen, wie sie in der Praxis auftreten, sind daher exakten Methoden, die stets die optimale Lösung liefern, nicht anwendbar. Da es die Online-Anwendung erfordert Lösungen in Echtzeit zu generieren, wurden im Rahmen dieser Arbeit nicht- exakte Methoden, sogenannte Heuristiken, entwickelt, mit deren Hilfe sehr gute Lösungen innerhalb kürzester Zeit gefunden werden können.

Die Basis unserer Methoden bilden lokale Suchheuristiken, welche die aktuelle Lösung mittels einfacher Ver- tauschoperationen iterativ verbessern. Bei der von uns betrachteten Anwendung besitzen die Zeitfenster, die als strukturierte Zeitfenster bezeichnet werden, spezielle Eigenschaften: Es wird angenommen, dass sich die Zeitfenster nicht überlappen und groß genug sind, damit mehrere Kunden innerhalb eines Zeitfensters besucht werden können. Diese Eigenschaften können ausgenutzt werden um den Suchraum der lokalen Operationen einzuschränken und somit unsere Heuristiken entscheidend zu beschleunigen.

Neben Lösungsqualität und Geschwindigkeit und der damit verbundenen ausgezeichneten Skalierbarkeit unserer Algorithmen, wurde von uns besonderer Wert auf die Flexibilität der entwickelten theoretischen Grundlagen gelegt. Dadurch können unsere Methoden jederzeit mit geringem Aufwand an eine Vielzahl von zusätzlichen spezifischen Bedingungen (sogenannte Business-Constraints), die es in der Praxis häufig und oftmals auch erst zu einem späteren Projektzeitpunkt zu berücksichtigen gilt, adaptiert werden.

Die vorgelegte Masterarbeit diente bisher als Ausgangspunkt mehrerer Konferenzvorträge und Publikationen. Bis dato sind zwei Konferenzpapiere entstanden, wobei eines davon bereits zur Veröffentlichung akzeptiert wurde [3] und das andere sich aktuell im Reviewprozess befindet [2]. Außerdem befindet sich derzeit ein Journalartikel [1] in Begutachtung, während ein weiterer Journalartikel in Kürze fertiggestellt wird.

Neben diesen akademischen Resultaten wurde die Praxisrelevanz der erarbeiten Ergebnisse bereits mehrfach unter Beweis gestellt. Die in dieser Arbeit entwickelten Methoden bilden die Grundlagen der Optimierungskom- ponente eines Systems für Online-Lebensmittelbestellungen, welches gemeinsam mit der britischen Firma Satalia für eine der weltweit größten Supermarktketten entwickelt wurde. Mit heutigem Tage befindet sich dieses System bereits in Betrieb und wird derzeit stufenweise in ganz Großbritannien eingeführt. Für weitere Details verweisen wir auf den folgenden, vor Kurzem veröffentlichten Artikel: http://tinyurl.com/cVRPsTW-article.

Literatur

[1] P. Hungerländer, K. Maier, J. Pöcher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle rou- ting problem with structured time windows. Technical Report TR-AAUK-M-O-16-12-30, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http://www.optimization-online.org/DB_HTML/2017/02/5859.html.

[2]  P. Hungerländer, A. Rendl, and C. Truden. On the slot optimization problem in on-line vehicle routing. Technical Report TR-AAUK-M-O-17-04-13, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http://www.optimization-online.org/DB_HTML/2017/04/ 5962.html.

[3]  P. Hungerländer, K. Maier, J. Pöcher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle routing problem with structured time windows. In Operations Research Proceedings 2016, 2017. Accepted, a preprint is available from http://www.optimization-online.org/DB_HTML/2016/12/5764.html.

Posted in News, Studienabgänger | Leave a comment

Content Generation and Practical Applications for Dynamic Adaptive Streaming over HTTP with a Focus on Mobile and Peer-Assisted Streaming

Lederer … ist der Titel einer der beiden besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakultät an der Universität Klagenfurt und wurde vom Förderverein Technische Fakultät mit EUR 1.000,– ausgezeichnet. Dem Autor und Preisträger, Herrn Mag. Dipl.-Ing. Stefan Lederer, wurde der Preis im Rahmen der Generalversammlung 2013 übergeben und die Arbeit wird hier kurz vorgestellt:

Im den letzten Jahren wurde adaptivem HTTP-Streaming viel Aufmerksamkeit geschenkt und mit Dynamic Adaptive Streaming over HTTP (DASH) steht hierzu nun auch ein internationaler MPEG-Standard zur Verfügung. Diesem Bereich widmen sich nun viele wissenschaftliche Arbeiten, jedoch werden größtenteils eigenen Inhalte, die nicht öffentlich verfügbar sind, als Basis für Untersuchungen verwendet, womit ein objektiver Vergleich, z.B. von Adaptionsalgorithmen, kaum möglich ist. Aus diesem Grund wurde im Rahmen dieser Arbeit eine öffentlich verfügbare Datenbasis für Experimente mit DASH erstellt und öffentlich bereitgestellt. In dieser Arbeit wird hierzu eine detaillierte Analyse der Content-Generierung für adaptive HTTP- Streaming-Systeme vorgestellt. Weiters wurde das Open Source Tool DASHEncoder entwickelt, mit welchem das vorgestellte Dataset erstellt wurde. Basierend auf dem Dataset wurde der Einfluss von Segmentlängen, sowie der Konfiguration von HTTP- Servern bzw. Verbindungen auf das Streaming evaluiert. Hierbei wird vor allem auf die Vor- und Nachteile sowie die optimalen Segmentlängen für die verschiedenen Szenarien eingegangen.

Zwei der wesentlichsten Merkmale von MPEG DASH sind die Datenübertragung auf Basis der vorhandenen HTTP-basierten Infrastruktur ohne spezialisierte Streamingserver, sowie die Fähigkeit der Anpassung an sich verändernde Bandbreitenbedingungen während des Streamings. Vor allem in mobilen Umgebungen hat diese Anpassbarkeit eine sehr hohe Relevanz. Daher wurde im Rahmen dieser Arbeit eine detaillierte Evaluierung der aktuellen Implementierung von MPEG DASH im Vergleich zu den populärsten proprietären Systeme (Microsoft Smooth Streaming, Adobe Dynamic Streaming und Apple HTTP Live Streaming) auf deren Einsetzbarkeit in sich bewegenden Fahrzeugen durchgeführt. Die hierbei erzielten Ergebnisse zeigen deutlich, dass MPEG-DASH sehr gut mit den

proprietären State-of-the-Art-Produkten konkurrieren kann und somit als eine ausgereifte Lösung für die Praxis betrachtet werden kann.

Darüber hinaus präsentiert diese Masterarbeit das Konzept des Peer-assisted DASH, welches das Ziel hat, den Upload einzelner Clients zu nützen um somit die Bandbreite und Infrastrukturkosten des Servers bzw. des Content-Delivery-Networks zu reduzieren. Hierbei wurde vor allem darauf geachtet, dass durch den Einsatz von Peer-assisted DASH die Standard-Konformität nicht beeinträchtigt wird. Weiters wird eine Evaluierung des Systems basierend auf einer Simulationsumgebung im Vergleich zu herkömmlichem DASH-Streaming vorgestellt, um die Umsetzbarkeit und das Potenzial von Peer-assisted DASH zu zeigen. Aus den Ergebnissen der Evaluierung ist ersichtlich, dass dieses Konzept eine Reduzierung der Bandbreite sowie der Infrastrukturkosten der Content-Provider um bis zu 25% bewirken kann. Hierbei werden die Kosteneinsparungen basierend auf den aktuellen Amazon- CloudFront-Preismodel berechnet, wodurch schlussendlich auch eine Brücke zu den Kostenbedürfnissen der Industrie geschlagen wird.

Teile dieser Arbeit wurden im Rahmen von drei internationalen Konferenzen veröffentlich und präsentiert:

  • Stefan Lederer, Christopher Müller and Christian Timmerer, “Towards Peer- Assisted Dynamic Adaptive Streaming over HTTP”, In Proceedings of the IEEE International Packet Video Workshop 2012, Munich, Germany, May 10- 11, 2012.
  • Christopher Müller, Stefan Lederer and Christian Timmerer, “An Evaluation of Dynamic Adaptive Streaming over HTTP in Vehicular Environments”, In Proceedings of the ACM Multimedia Systems Conference 2012 and the 4th ACM Workshop on Mobile Video, Chapel Hill, North Carolina, February 24, 2012.
  • Stefan Lederer, Christopher Müller and Christian Timmerer, “Dynamic Adaptive Streaming over HTTP Dataset”, In Proceedings of the ACM Multimedia Systems Conference 2012, Chapel Hill, North Carolina, February 22-23, 2012.

Posted in News, Studienabgänger | Leave a comment

On a Sampling Decision System using Virtual Metrology

SONY DSC … ist der Titel einer der beiden besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakultät an der Universität Klagenfurt und wurde vom Förderverein Technische Fakultät mit EUR 1.000,– ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Daniel Kurz, wurde der Preis im Rahmen der Generalversammlung 2013 übergeben und die Arbeit wird hier kurz vorgestellt:

The common approach to semiconductor process control is based on physical measurements of a certain number of processed wafers. Therefore, the status of the process is just controlled within certain time lags, which might result in delayed observations of process abnormalities. Moreover, the measurement rules are typically of a statical nature meaning that the measurement policy is not adapted to current production conditions. In this master thesis, we propose a novel approach to semiconductor process control based on virtual measurements. These are predictions on the location of the real measurements in the control chart depending on the status of the equipment while processing. The advantage of the application of virtual measurements is that they are available for every wafer. Therefore, the status of the process can be steadily controlled and process deviations can be realized earlier. Moreover, the usage of virtual measurements allows for adapting the measurement policy to current process conditions. Whenever virtual measurements provide sufficiently strong evidence that the process is running within the control limits, there is no need of triggering physical measurements. However, if process abnormalities are signalized by the virtual measurement, a physical measurement needs to be triggered. Therefore, physical metrology operations can be scheduled in a more efficient way.

Posted in News, Studienabgänger | Leave a comment

A Bundle Method for the Traveling Salesman Problem

… ist der Titel der besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakultät an der Universität Klagenfurt und wurde vom Förderverein Technische Fakultät mit EUR 1500,– ausgezeichnet. Der Autorin und Preisträgerin, Frau Dipl.-Ing. Karin Kruggel, wurde der Preis im Rahmen der Eröffnung des akademischen Jahres 2011/2012 übergeben und die Arbeit wird hier kurz vorgestellt:

Das Rundreiseproblem, auch als Problem des Handlungsreisenden, kurz TSP, bekannt, ist ein kombinatorisches Optimierungsproblem. Dieses mathematische Problem ist sehr einfach zu beschreiben. Die Aufgabe besteht darin eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die Gesamtreisestrecke nach der Rückkehr zum Ausgangspunkt möglichst kurz ist. Weiters muss jeder Ort genau einmal besucht werden.

Die einfache Beschreibung dieses Problems macht das TSP zur idealen Plattform um neue algorithmische Ideen zu entwickeln. Daher ist das Traveling Salesman Problem wohl eines der populärsten und meist erforschten Probleme der Mathematik.

Derartige Fragestellungen spielen in der Praxis eine große Rolle wie beispielsweise im Design von Mikrochips, der Verteilung von Waren, der kostenoptimalen Belegung von Maschinen, bei der optimalen Wegplanung eines Bohrers auf einer Leiterplatte oder bei der Tourenplanung eines Kunden- oder Pannendienstes. In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie eingeschränkte Ressourcen, Zeitfenster oder automatisierte Bohrer, die sich nur vertikal und horizontal bewegen können beachtet werden, was die Lösung des Problems erheblich erschwert.

Die Probleme mit denen man sich in der kombinatorischen Optimierung beschäftigt sind meist sehr schwierig. Komplexitätstheoretisch gehört das TSP zur Klasse der NP-vollständigen Probleme. Es stellt sich die Frage, wie man mit solchen Problemen umgeht, da es für diese Klasse von Problemen keine effizienten Algorithmen gibt. Die Laufzeit des worst-case-Szenarios jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, hängt im besten Fall exponentiell von der Anzahl der Städte ab. Solch ein Algorithmus benötigt bereits für eine geringe Anzahl von Städten enorm viel Zeit. Aus diesem Grund ist man an der Berechnung von guten und zufrieden stellenden Approximationen interessiert.

Zur Lösung dieser Optimierungsprobleme können Methoden der differenzierbaren Optimierung wie das Verfahren des steilsten Abstiegs nicht angewendet werden, weil mathematische Eigenschaften wie Stetigkeit und Differenzierbarkeit in der kombinatorischen Optimierung nicht gelten. In der Literatur wird zur Minimierung von nichtglatten Funktionen häufig auf die Subgradienten Methode verwiesen. Die Idee meiner Masterarbeit war es für die Minimierung anstatt dieser die Bundle Methoden zu verwenden.

Das Ziel war es mit Hilfe der Bundle Methoden eine gute untere Schrankenberechnung für das TSP zu finden. Umfangreiche numerische Berechnungen lieferten sehr gute Resultate und zeigten die praktische Brauchbarkeit dieses Zugangs. So konnte zum Beispiel bei einem getesteten Städteproblem mit 2392 Knoten eine untere Schranke von lediglich 1,19 Prozent Abweichung zur optimalen Rundreise gefunden werden. Weiters wurde bei einer Problemgröße von 100 zufällig gewählten Knoten eine Abweichung von 0,13 Prozent zum Optimum erzielt.
Zusammenfassend kann somit gesagt werden, dass die Bundle Methoden eine gute Wahl zur Berechnung von brauchbaren unteren Schranken für das Rundreiseproblem darstellen.

Posted in News, Studienabgänger | Leave a comment

TEWI-High-Performer ausgezeichnet und Förderpreis der Technischen Fakultät vergeben

Im Rahmen der Eröffnung des akademischen Jahres 2010/2011 am 14. Oktober hat der Förderverein Technische Fakultät die TEWI-High-Performer, als Co-Sponsor gemeinsam mit der Firma Windtec GmbH, ausgezeichnet und den Förderpreis der Technischen Fakultät vergeben.

In Anerkennung für ihre Leistungen aus dem vergangenen Studienjahr, wurden die »Best Performers« der vier Studienrichtungen der Technischen Fakultät an der Universität Klagenfurt mit, einem von der Firma Windtec GmbH und dem Förderverein Technische Fakultät gestifteten Preis, ausgezeichnet, wobei ECTS und Noten aller Beurteilungen berücksichtigt wurden. Je EUR 500,– und eine Universitätsnadel in Silber erhielten

  • Stefan Lederer (Informatik)
  • Harald Saupper (Informationsmanagement)
  • Daniel Kurz (Technische Mathematik)
  • Dominik Daniel Egarter (Informationstechnik)
  • Stefan Mak wurde als bester Student der Fakultät der technischen Wissenschaften ausgezeichnet

Der diesjährige Förderpreis der Technischen Fakultät (gestiftet vom Förderverein Technische Fakultät) für die beste Diplom- bzw. Magisterarbeit aller Studien der Technischen Fakultät an der Universität Klagenfurt erhielten Herr DI Hendrik Husstedt (»Kalibrierung eines Referenzsensors zur ortsabhängigen Erfassung inhomogener Magnetfelder«). Er wurde mit EUR 1.500,– ausgezeichnet.

Wir gratulieren recht herzlich!

zp8497586rq
Posted in News, Studienabgänger | Tagged , | Kommentare deaktiviert für TEWI-High-Performer ausgezeichnet und Förderpreis der Technischen Fakultät vergeben

TEWI-High-Performer ausgezeichnet und Förderpreis der Technischen Fakultät vergeben

img_4435_webIm Rahmen der Eröffnung des akademischen Jahres 2010/2011 hat der Förderverein Technische Fakultät die TEWI-High-Performer, als Co-Sponsor gemeinsam mit IBM, ausgezeichnet und den Förderpreis der Technischen Fakultät vergeben.

In Anerkennung für ihre Leistungen aus dem vergangenen Studienjahr, wurden die »Best Performers« der vier Studienrichtungen der Technischen Fakultät an der Universität Klagenfurt mit, einem von IBM und dem Förderverein Technische Fakultät gestifteten Preis, ausgezeichnet, wobei ECTS und Noten aller Beurteilungen berücksichtigt wurden. Je EUR 500,– und eine Universitätsnadel in Silber erhielten
ibm

  • Robert Göritzer* (Bachelor-Studium Informatik, 283 Punkte)
  • Günther Repitsch (Bachelor-Studium Informationsmanagement, 326 Punkte)
  • Evamaria Ruß (Bachelor-Studium Technische Mathematik, 365 Punkte)
  • Christoph Unterrieder (Bachelor-Studium Informationstechnik, 245 Punkte)

Der diesjährige Förderpreis der Technischen Fakultät (gestiftet vom Förderverein Technische Fakultät) für die beste Diplom- bzw. Magisterarbeit aller Studien der Technischen Fakultät an der Universität Klagenfurt erhielten Frau DI Daniela Pohl (»Specification Comprehension – Konzeptverwaltung am Beispiel zustandsbasierter Spezifikationen«) und Herr DI Markus Aschinger** (»Constraint-based Composition of Recommendations«). Sie wurden mit jeweils EUR 750,– ausgezeichnet.

Wir gratulieren recht herzlich!

* … befindet sich derzeit auf Praxissemester an der TU Delft. Preis wurde entgegen genommen von seinen Eltern.
** … ist nach Oxford gewechselt um dort an seiner Dissertation zu arbeiten. Preis wurde entgegen genommen von Andreas Griesser, langjähriger Bürokollege an der Universität Klagenfurt.

Posted in News, Studienabgänger | Tagged , | Leave a comment