@phdthesis{317,
  author       = {{Jähn, Claudius}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen}}},
  year         = {{2015}},
}

@phdthesis{270,
  author       = {{Abshoff, Sebastian}},
  publisher    = {{Universität Paderborn}},
  title        = {{{On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks}}},
  year         = {{2015}},
}

@phdthesis{19039,
  author       = {{Petring, Ralf}},
  title        = {{{Multi-Algorithmen-Rendering: Darstellung heterogener 3-D-Szenen in Echtzeit}}},
  year         = {{2014}},
}

@phdthesis{431,
  abstract     = {{In meiner Dissertation besch{\"a}ftige ich mich mit dem Entwurf und der Analyse energieeffizienter Schedulingalgorithmen, insbesondere f{\"u}r sogenannte Speed-Scaling Modelle. Diese stellen das theoretische Pendant von Techniken wie AMDs PowerNOW! und Intels SpeedStep dar, welche es erlauben die Geschwindigkeit von Prozessoren zur Laufzeit an die derzeitigen Bedingungen anzupassen. Theoretische Untersuchungen solcher Modelle sind auf eine Arbeit von Yao, Demers und Shenker (FOCS'95) zur{\"u}ckzuf{\"u}hren. Hier kombinieren die Autoren klassisches Deadline-Scheduling mit einem Prozessor der Speed-Scaling beherrscht. Es gilt Jobs verschiedener Gr{\"o}ße fristgerecht abzuarbeiten und die dabei verwendete Energie zu minimieren. Der Energieverbrauch des Prozessors wird durch eine konvexe Funktion $\POW\colon\R_{\geq0}\to\R_{\geq0}$ modelliert, welche die Geschwindigkeit auf den Energieverbrauch abbildet.Meine Dissertation betrachtet verschiedene Varianten des urspr{\"u}nglichen Speed-Scaling Modells. Forschungsrelevante Ergebnisse sind in den Kapiteln 3 bis 6 zu finden und erstrecken sich {\"u}ber die im Folgenden beschriebenen Aspekte:- Kapitel 3 und 4 betrachten verschiedene \emph{Price-Collecting} Varianten des Originalproblems. Hier d{\"u}rfen einzelne Deadlines verfehlt werden, sofern eine jobabh{\"a}ngige Strafe gezahlt wird. Ich entwerfe insbesondere Online-Algorithmen mit einer beweisbar guten Competitiveness. Dabei liefern meine Ergebnisse substantielle Verbesserungen bestehender Arbeiten und erweitern diese unter Anderem auf Szenarien mit mehreren Prozessoren.- In Kapitel 5 wird statt des klassischen Deadline-Schedulings eine Linearkombination der durchschnittlichen Antwortzeit und des Energieverbrauchs betrachtet. Die Frage, ob dieses Problem NP-schwer ist, stellt eine der zentralen Forschungsfragen in diesem Gebiet dar. F{\"u}r eine relaxierte Form dieser Frage entwerfe ich einen effizienter Algorithmus und beweise seine Optimalit{\"a}t.- Das letzte Kapitel betrachtet ein Modell, welches – auf den ersten Blick – nicht direkt zur Speed-Scaling Literatur z{\"a}hlt. Hier geht es stattdessen um ein allgemeines Resource-Constrained Scheduling, in dem sich die Prozessoren zusammen eine gemeinsame, beliebig aufteilbare Ressource teilen. Ich untersuche die Komplexit{\"a}t des Problems und entwerfe verschiedene Approximationsalgorithmen.}},
  author       = {{Kling, Peter}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Energy-efficient Scheduling Algorithms}}},
  year         = {{2014}},
}

@phdthesis{17440,
  author       = {{Eikel, Benjamin}},
  title        = {{{Spherical visibility sampling : preprocessed visibility for occlusion culling in complex 3D scenes}}},
  year         = {{2013}},
}

@phdthesis{514,
  abstract     = {{Diese Arbeit besch{\"a}ftigt sich mit dem Facility Location Problem. Dies ist ein Optimierungsproblem, bei dem festgelegt werden muss an welchen Positionen Ressourcen zur Verf{\"u}gung gestellt werden, so dass diese von Nutzern gut erreicht werden k{\"o}nnen. Es sollen dabei Kosten minimiert werden, die zum einen durch Bereitstellung von Ressourcen und zum anderen durch Verbindungskosten zwischen Nutzern und Ressourcen entstehen. Die Schwierigkeit des Problems liegt darin, dass man einerseits m{\"o}glichst wenige Ressourcen zur Verf{\"u}gung stellen m{\"o}chte, andererseits daf{\"u}r sorgen muss, dass sich Nutzer nicht all zu weit weg von Ressourcen befinden. Dies w{\"u}rde n{\"a}mlich hohe Verbindungskosten nach sich ziehen. Das Facility Location Problem wurde bereits sehr intensiv in vielen unterschiedlichen Varianten untersucht. In dieser Arbeit werden drei Varianten des Problems modelliert und neue Algorithmen f{\"u}r sie entwickelt und bez{\"u}glich ihres Approximationsfaktors und ihrer Laufzeit analysiert. Jede dieser drei untersuchten Varianten hat einen besonderen Schwerpunkt. Bei der ersten Varianten handelt es sich um ein Online Problem, da hier die Eingabe nicht von Anfang an bekannt ist, sondern Schritt f{\"u}r Schritt enth{\"u}llt wird. Die Schwierigkeit hierbei besteht darin unwiderrufliche Entscheidungen treffen zu m{\"u}ssen ohne dabei die Zukunft zu kennen und trotzdem eine zu jeder Zeit gute L{\"o}sung angeben zu k{\"o}nnen. Der Schwerpunkt der zweiten Variante liegt auf Lokalit{\"a}t, die z.B. in Sensornetzwerken von großer Bedeutung ist. Hier soll eine L{\"o}sung verteilt und nur mit Hilfe von lokalen Information berechnet werden. Schließlich besch{\"a}ftigt sich die dritte Variante mit einer verteilten Berechnung, bei welcher nur eine stark beschr{\"a}nkte Datenmenge verschickt werden darf und dabei trotzdem ein sehr guter Approximationsfaktor erreicht werden muss. Die bei der Analyse der Approximationsfaktoren bzw. der Kompetitivit{\"a}t verwendeten Techniken basieren zum großen Teil auf Absch{\"a}tzung der primalen L{\"o}sung mit Hilfe einer L{\"o}sung des zugeh{\"o}rigen dualen Problems. F{\"u}r die Modellierung von Lokalit{\"a}t wird das weitverbreitete LOCAL Modell verwendet. In diesem Modell werden f{\"u}r die Algorithmen subpolynomielle obere Laufzeitschranken gezeigt.}},
  author       = {{Pietrzyk, Peter}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Local and Online Algorithms for Facility Location}}},
  year         = {{2013}},
}

@phdthesis{601,
  abstract     = {{Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen Gel{\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\"u}ssen sich selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen. In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden k{\"o}nnen. Daf{\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden obere und untere Schranken f{\"u}r die ben{\"o}tigte Anzahl Runden und die Bewegungsdistanz gezeigt. In einigen F{\"a}llen wird außerdem die ben{\"o}tigte Bewegungsdistanz mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie auf der gleichen Instanz ben{\"o}tigen w{\"u}rde. So werden kompetititve Faktoren hergeleitet.}},
  author       = {{Kempkes, Barbara}},
  isbn         = {{978-3-942647-21-2}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Local strategies for robot formation problems}}},
  volume       = {{302}},
  year         = {{2012}},
}

@phdthesis{19619,
  author       = {{Korzeniowski, Miroslaw}},
  isbn         = {{978-3-942647-08-3}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Dynamic Load Balancing in Peer-to-Peer Networks}}},
  volume       = {{289}},
  year         = {{2011}},
}

@phdthesis{18974,
  author       = {{Mehler, Jan}},
  isbn         = {{978-3-942647-06-9}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Power-Aware Online File Allocation in Dynamic Networks}}},
  volume       = {{287}},
  year         = {{2011}},
}

@phdthesis{19040,
  author       = {{Effert, Sascha}},
  title        = {{{Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen}}},
  year         = {{2011}},
}

@misc{663,
  author       = {{Swierkot, Kamil}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Complexity Classes for Local Computation}}},
  year         = {{2011}},
}

@phdthesis{18910,
  author       = {{Bienkowski, Marcin}},
  isbn         = {{978-3-942647-01-4}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Page migration in dynamic networks}}},
  volume       = {{282}},
  year         = {{2010}},
}

@phdthesis{18927,
  author       = {{Dynia, Miroslaw}},
  isbn         = {{978-3-942647-03-8}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Collective graph exploration}}},
  volume       = {{284}},
  year         = {{2010}},
}

@phdthesis{19041,
  author       = {{Mahlmann, Peter}},
  isbn         = {{978-3-942647-02-1}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Peer-to-peer networks based on random graphs}}},
  volume       = {{283}},
  year         = {{2010}},
}

@phdthesis{19042,
  author       = {{Degener, Bastian}},
  isbn         = {{978-3-939350-97-2 }},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Local, distributed approximation algorithms for geometric assignment problems}}},
  volume       = {{278}},
  year         = {{2010}},
}

@phdthesis{19605,
  author       = {{Lürwer-Brüggemeier, Katharina}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division}}},
  volume       = {{261}},
  year         = {{2009}},
}

@phdthesis{19614,
  author       = {{Mense, Mario}},
  isbn         = {{978-3-939350-79-8}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{On Fault-Tolerant Data Placement in Storage Networks}}},
  volume       = {{260}},
  year         = {{2009}},
}

@phdthesis{19617,
  author       = {{Kortenjan, Michael}},
  isbn         = {{978-3-939350-77-4}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes}}},
  volume       = {{258}},
  year         = {{2009}},
}

@phdthesis{19618,
  author       = {{Bonorden, Olaf}},
  isbn         = {{978-3-939350-76-7}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip}}},
  volume       = {{257}},
  year         = {{2009}},
}

@phdthesis{19615,
  author       = {{Schomaker, Gunnar}},
  isbn         = {{978-3-939350-78-1}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Distributed Resource Allocation and Management in Heterogeneous Networks}}},
  volume       = {{259}},
  year         = {{2008}},
}