Algorithms for knapsacks, paths and strings

Abstract

In this thesis we study three problems: 1. Knapsack: The Knapsack problem is a classic combinatorial optimization problem. We give a collection of improved exact and approximation algorithms for Knapsack and some of its variants. Our study is guided by the connection between Knapsack and min-plus convolution, a central problem in fine-grained complexity. 2. Sublinear Edit Distance: The edit distance is a popular and practically motivated measure of similarity between texts. We focus on sublinear-time algorithms, which aim to approximate the edit distance k of two texts without reading them entirely. Our main result is a k^{o(1)}-approximation in time O(n/k +k^{2+o(1)}). This constitutes a quadratic improvement over the previous state of the art, and matches an unconditional lower bound for small k (up to subpolynomial factors in the running time and approximation factor). 3. Negative Weight Single-Source Shortest Paths: Computing shortest paths from a source in a weighted directed graph is a fundamental problem. When all edge weights are nonnegative, the classic Dijkstra’s algorithm solves this problem in near-linear time. It has been a long-standing open question to obtain a near-linear time algorithm when the graph contains negative edge weights. This has been solved recently in a breakthrough by Bernstein, Nanongkai and Wulff-Nilsen, who presented an algorithm in time O(m log^8(n) log(W)). Our contribution is an improvement by nearly 6 log factors.

In dieser Doktorarbeit untersuchen wir drei Probleme: 1. Knapsack: Knapsack ist ein klassisches kombinatorisches Optimierungsproblem. Wir präsentieren eine Sammlung von verbesserten exakten und approximativen Algorithmen für Knapsack und einige seiner Varianten. Unsere Studie wird geleitet von der Verbindung zwischen Knapsack und der Min-Plus-Faltung, einem zentralen Problem der feinkörnigen Komplexität. 2. Sublineare Editierdistanz: Die Editierdistanz ist ein beliebtes und praktisch motiviertes Maß für die Ähnlichkeit zwischen Texten. Wir konzentrieren uns auf Algorithmen mit sublinearer Zeit, die darauf abzielen, die Editierdistanz k von zwei Texten zu approximieren, ohne sie vollständig zu lesen. Unser Hauptergebnis ist eine k^{o(1)}-Approximation in der Zeit O(n/k +k^{2+o(1)}). Dies stellt eine quadratische Verbesserung gegenüber dem bisherigen Stand der Technik dar und entspricht einer unbedingten unteren Schranke für kleine k (bis auf Subpolynomialfaktoren in der Laufzeit und im Approximationsfaktor). 3. Negativ gewichtete kürzeste Pfade von einer Quelle: Die Berechnung der kürzesten Pfade von einer Quelle in einem gewichteten gerichteten Graphen ist ein grundlegendes Problem. Wenn alle Kantengewichte nicht-negativ sind, löst der klassische Dijkstra-Algorithmus dieses Problem in nahezu linearer Zeit. Es ist seit langem eine offene Frage, einen Algorithmus mit nahezu linearer Zeit zu erhalten wenn der Graph negative Kantengewichte enthält. Diese Frage wurde kürzlich in einem Durchbruch von Bernstein, Nanongkai und Wulff-Nilsen beantwortet, mit einen Algorithmus in der Zeit O(m log^8(n) log(W)). Unser Beitrag ist eine Verbesserung um fast 6 log-Faktoren.