On efficiency and reliability in computer science

Abstract

Efficiency of algorithms and robustness against mistakes in their implementation or uncertainties in their input has always been of central interest in computer science. This thesis presents results for a number of problems related to this topic. Certifying algorithms enable reliable implementations by providing a certificate with their answer. A simple program can check the answers using the certificates. If the the checker accepts, the answer of the complex program is correct. The user only has to trust the simple checker. We present a novel certifying algorithm for 3-edge-connectivity as well as a simplified certifying algorithm for 3-vertex-connectivity. Occasionally storing the state of computations, so called checkpointing, also helps with reliability since we can recover from errors without having to restart the computation. In this thesis we show how to do checkpointing with bounded memory and present several strategies to minimize the worst-case recomputation. In theory, the input for problems is accurate and well-defined. However, in practice it often contains uncertainties necessitating robust solutions. We consider a robust variant of the well known k-median problem, where the clients are grouped into sets. We want to minimize the connection cost of the expensive group. This solution is robust against which group we actually need to serve. We show that this problem is hard to approximate, even on the line, and evaluate heuristic solutions.

Effizienz von Algorithmen und Zuverlässigkeit gegen Fehlern in ihrer Implementierung oder Unsicherheiten in der Eingabe ist in der Informatik von großem Interesse. Diese Dissertation präsentiert Ergebnisse für Probleme in diesem Themenfeld. Zertifizierende Algorithmen ermöglichen zuverlässige Implementierungen durch Berechnung eines Zertifikats für ihre Antworten. Ein einfaches Programm kann die Antworten mit den Zertifikaten überprüfen. Der Nutzer muss nur dem einfachen Programms vertrauen. Wir präsentieren einen neuen zertifizierenden Algorithmus für 3-Kantenzusammenhang und einen vereinfachten zertifizierenden Algorithmus für 3-Knotenzusammenhang. Den Zustand einer Berechnung gelegentlich zu speichern, sog. Checkpointing, verbessert die Zuverlässigkeit. Im Fehlerfall kann ein gespeicherter Zustand wiederhergestellt werden ohne die Berechnung neu zu beginnen. Wir zeigen Strategien für Checkpointing mit begrenztem Speicher, die die Neuberechnungszeit minimieren. Traditionell sind die Eingaben für Probleme präzise und wohldefiniert. In der Praxis beinhalten die Eingaben allerdings Unsicherheiten und man braucht robuste Lösungen. Wir betrachten eine robuste Variante des k-median Problem. Hier sind die Kunden in Gruppen eingeteilt und wir möchten die Kosten der teuersten Gruppe minimieren. Dies macht die Lösung robust gegenüber welche der Gruppen letztlich bedient werden soll. Wir zeigen, dass dieses Problem schwer zu approximieren ist und untersuchen Heuristiken.