49 Arbeiten
Diese Arbeit untersucht die Machbarkeit von Quantenalgorithmen zur Lösung der 3D-heterogenen Poisson-Gleichung für Frakturströmungen, zeigt dabei zwar eine exponentielle Speicherersparnis und eine verbesserte Laufzeit gegenüber klassischen Methoden, identifiziert jedoch die begrenzte Wirksamkeit von Vorkonditionierung bei der Blockkodierung als entscheidendes Hindernis für den vollen Quantenvorteil.
Die Arbeit stellt die ersten Approximationsalgorithmen für zwei Verallgemeinerungen des Maximum Quadratic Assignment Problems vor, nämlich das Maximum List-Restricted Quadratic Assignment Problem und das Maximum Quadratic -Matching Assignment Problem, und liefert dabei randomisierte Approximationsfaktoren von bzw. .
Die Arbeit zeigt, dass das robuste Permutations-Fließshop-Problem unter Budgetunsicherheit durch die Lösung einer polynomiellen Anzahl von Nominalproblemen gelöst werden kann, was zu einem polynomiellen exakten Algorithmus für zwei Maschinen und einer polynomiellen Approximation für eine beliebige feste Anzahl von Maschinen führt.
Die Autoren stellen ein allgemeines Framework für „s-of-k"-Spiele vor, bei denen Spieler Punkte für das Besetzen eines Teils einer Gewinnmenge erhalten, und analysieren die erreichbaren Punktzahlen unter optimaler sowie unter Paarungsstrategie auf verschiedenen regelmäßigen Gittern.
Diese Arbeit untersucht minimal harte Graphen in der Klasse der schwach chordalen Graphen und liefert vollständige Klassifizierungen für mehrere ihrer Untergruppen, was zudem zu vereinfachten Beweisen bestehender Ergebnisse führt.
Die Arbeit untersucht strukturelle Eigenschaften kürzester Flip-Sequenzen zwischen ebenen aufspannenden Bäumen in konvexer Position und widerlegt dabei die „Parking Edge"- und „Reparking"-Vermutungen für den allgemeinen Fall, während sie deren Gültigkeit in spezifischen Szenarien bestätigt.
Diese Arbeit charakterisiert algebraisch eine Teilmenge reversibler zellulärer Automaten ersten Grades über unter Nullrandbedingungen, indem sie zeigt, dass die Reversibilität für beliebige Gittergrößen durch die Überprüfung von nur drei algebraischen Bedingungen in konstanter Zeit bestimmt werden kann.
Die Arbeit präsentiert einen $2^{O(k \log k)} n$-zeitlichen Algorithmus für das Optimal-Morse-Matching-Problem auf CW-Komplexen mit beschränkter Baumweite und beweist unter der Annahme der Exponentialzeit-Hypothese, dass keine wesentlich schnellere Lösung existiert.
Diese Arbeit stellt den ersten algorithmischen Ansatz vor, der die Approximationsgüte des Greedy-Algorithmus für die submodulare Maximierung über dem Schnitt von Matroiden durch eine hybride Greedy-Lokalsuche-Methode um einen konstanten Faktor verbessert und dabei in polynomieller Zeit unabhängig von läuft.