Barrier resilience problems

Abstract

The barrier resilience problem can be stated as follows: Given two points s and t and a set of unit disks D in 2D-space, what is the minimum number of disks k that a curve connecting s and t must cross. It is currently unknown if there exists a polynomial time algorithm that can find the optimal solution k for any problem instance. This work aims to give an intuition on why it is difficult to solve and at the same time show some restrictions on the complexity, which prevent an easy reduction of NP-hard problems. As a result, neither a polynomial time algorithm nor a reduction of an NP-hard problem is currently known or discovered in this work. Existing ideas and approximations are explained and expanded upon, whilst also introducing novel algorithms. One technique used is linear programming, which was not previously considered for solving the barrier resilience problem. In contrast to previous works, the algorithms offer both upper and lower bounds for k, which are very useful in practice in restricting k to a small range of values, even restricting this range to only the optimal value k in most randomly generated instances. Existing and novel algorithms are implemented in C++. The different approximations are compared both theoretically and practically, with their performance in terms of runtime and accuracy being measured on random instances.

Das 'Barrier Resilience'-Problem lautet wie folgt: Gegeben sind zwei Punkte s und t und eine Menge von Einheitskreisen D im zweidimensionalen Raum. Die Frage ist nun, was die geringste Anzahl an Kreisen k ist, die eine Kurve von s nach t schneiden muss. Es ist zurzeit unbekannt, ob es einen Algorithmus gibt, der die optimale Lösung k für jede Probleminstanz in Polynomialzeit findet. In dieser Arbeit wird eine Intuition vermittelt, weshalb das Problem schwer zu lösen ist. Gleichzeitig werden Restriktionen aufgezeigt, die eine einfache Reduktion eines NP-Schweren Problems verhindern. Deshalb wird auch in dieser Arbeit weder ein Algorithmus gefunden, der das Problem in Polynomialzeit löst, noch gelingt eine solche Reduktion. Vorherige Ideen und Algorithmen werden erklärt und erweitert, aber auch neue Algorithmen werden eingeführt. Eine Technik hierbei ist die lineare Programmierung, welche bisher noch nicht zur Lösung des 'barrier resilience' Problems herangezogen wurde. Im Gegensatz zu vorherigen Arbeiten liefern die vorgestellten Algorithmen Ober- und Untergrenzen, die k in der Praxis sehr gut einschränken und in den meisten zufällig generierten Instanzen sogar nur den optimalen Wert k zulassen. Existierende und neue Algorithmen werden in C++ implementiert. Sie werden theoretisch als auch praktisch verglichen, wobei ihr Ergebnis im Bezug auf Laufzeit und Approximationsfaktor an zufällig generierten Instanzen gemessen wird.