91 Arbeiten
Die Arbeit stellt den Huffman-Bucket-Sketch vor, eine speichereffiziente und zusammenführbare Datenstruktur, die HyperLogLog-Sketches durch verlustlose Huffman-Kodierung der Registerwerte in Bits komprimiert und dabei amortisierte konstante Update-Zeiten sowie Merge-Fähigkeit beibehält.
Der Artikel untersucht minimale unerfüllbare Teilmengen von 2-CNF-Formeln, indem er einen linearen Erkennungsalgorithmus für 2-MUs vorstellt, die Komplexität des Findens spezifischer MUS-Varianten analysiert und einen inkrementellen Polynomzeit-Algorithmus für MUSs mit mindestens einer Unit-Klausel entwickelt.
Die Arbeit stellt den Block Sparse Tensor Train (BSTT)-Sketch vor, einen strukturierten zufälligen Projektionsoperator, der durch lineare Skalierung in Bezug auf die Tensorordnung und die Subraumdimension eine effiziente und theoretisch fundierte Approximation für Tensor-Train-Formate ermöglicht.
Diese Arbeit löst eine offene Frage von Jain et al., indem sie erstmals ein Problem vorstellt, das die Differential-Privacy unter kontinuierlicher Beobachtung in den oblivious und adaptiven Settings trennt, indem sie zeigt, dass ein oblivious Algorithmus über exponentiell viele Zeitschritte hinweg genau bleibt, während jeder adaptive Algorithmus bereits nach konstant vielen Schritten ungenau wird.
Das Paper stellt IsalGraph vor, eine Methode zur kompakten Darstellung beliebiger endlicher Graphen als Zeichenkette über einem neun Zeichen umfassenden Alphabet, die durch einen kleinen virtuellen Maschinencode erzeugt wird, isomorphieinvariant ist und eine starke Korrelation zwischen dem Levenshtein-Abstand der Strings und dem Graph-Edit-Abstand aufweist.
Die Autoren nutzen erweiterte Methoden des Graph-Containings, um nahezu optimale Schranken für die Stichprobenkomplexität beim Testen der -Clique-Eigenschaft und der -Färbbarkeit in dichten Graphen zu etablieren.
Dieses Paper untersucht das Online-Scheduling von Jobs auf heterogenen Maschinen, indem es einen 8-kompetitiven Algorithmus für Einheitsjobs entwickelt und eine untere Schranke von 2 für das Wettbewerbsverhältnis nachweist, um die Kosten in Cloud-Umgebungen zu minimieren.
Die Autoren präsentieren einen FPT-Algorithmus, der das Problem der Pfadüberdeckung in ungerichteten Graphen löst und damit eine algorithmische Verallgemeinerung des Gallai-Milgram-Theorems sowie den ersten polynomiellen Nachweis für die Hamiltonizität bei Graphen mit einer Unabhängigkeitszahl von höchstens drei ermöglicht.
Die Arbeit stellt -Motif vor, einen GPU-beschleunigten Algorithmus für das Subgraph-Isomorphie-Problem, der Graphen in tabellarische Form überführt und durch skalierbare Datenbankoperationen eine bis zu 595-fache Beschleunigung gegenüber traditionellen Methoden wie VF2 erreicht.
Diese Arbeit stellt und evaluiert speichereffiziente B-Baum-Varianten für ressourcenbeschränkte Flash-Embedded-Geräte, die eine effiziente On-Device-Datenverarbeitung im IoT-Kontext ermöglichen.
Diese Arbeit stellt die ersten streng in-place Sortieralgorithmen vor, die mit einer Laufzeit von O(n(1 + H(A))) optimal an der Laufzeit-Entropie des Eingabearrays orientiert sind und sich insbesondere für speicherbeschränkte eingebettete Systeme wie Kühlschränke eignen.
Diese Arbeit verbessert die bekannten Schranken für das agnostische Lernen von Konzeptklassen mit begrenzter Gaußscher Oberflächenfläche, indem sie zeigt, dass ein Polynomgrad von ausreicht, was zu nahezu optimalen Komplexitätsergebnissen für das Lernen von Polynom-Threshold-Funktionen im statistischen Abfragemodell führt.
Die Arbeit zeigt, dass ein bisher nicht betrachteter gieriger Algorithmus für das Online-Paketweiterleitungsproblem in einem Linien-Netzwerk mit Paketen, die genau einen oder zwei Router durchlaufen müssen, eine exakte Wettbewerbsfähigkeit von $2-2^{1-k}4/3$.
Die Arbeit stellt einen neuen Algorithmus zur Bestimmung des transversalen Rangs von Hypergraphen mit verbesserter Laufzeitabhängigkeit von der Kantenanzahl vor, entwickelt eine „Look-ahead"-Methode zur Enumeration minimaler Treffermengen und zeigt, dass eine weitere Laufzeitoptimierung äquivalent zu mehreren bahnbrechenden Fortschritten in der kombinatorischen Algorithmik ist.
Diese Arbeit stellt die ersten bekannten konstanten Approximationsalgorithmen für das parallele Token-Swapping-Problem auf für Quantencomputer relevanten Graphentopologien vor, untersucht die Güte natürlicher Untergrenzen und behandelt zudem die farbige Variante des Problems, bei der ununterscheidbare Token vorkommen.
Dieser Artikel liefert den ersten rigorosen Beweis für die PLS-Vollständigkeit des -Opt-Lokalsuchalgorithmus für das Traveling-Salesman-Problem und reduziert die erforderliche Konstante dabei drastisch auf , wodurch eine offene Frage von Monien, Dumrauf und Tscheuschner beantwortet wird.
Die Autoren beweisen eine abgeschwächte Version einer Vermutung von Chudnovsky et al., indem sie zeigen, dass Graphen, die und das Gitter als induzierte Minoren ausschließen, eine Baumszerlegung besitzen, deren Taschen eine beschränkte Unabhängigkeitszahl bezüglich großer Distanzen aufweisen.
Die vorgestellte Arbeit entwickelt ein sequenzielles Verfahren zur Generierung, Enumeration und Stichprobenziehung von bipartiten, gerichteten und ungerichteten Graphen mit vorgegebenen Gradfolgen, das durch eine notwendige und hinreichende Intervallbedingung die globale Durchführbarkeit garantiert und sich durch hohe Skalierbarkeit bei großen Instanzen auszeichnet.
Die Arbeit stellt den Transfer Aware Dijkstra (TAD) vor, einen optimierten Dijkstra-Algorithmus, der durch die Berücksichtigung von Pufferzeiten an Haltestellen und das Scannen ganzer Trip-Sequenzen die Unzulänglichkeiten früherer Filtermethoden behebt und dabei sowohl optimale Ergebnisse als auch eine mehr als zweifache Geschwindigkeitssteigerung gegenüber dem RAPTOR-basierten MR-Algorithmus liefert.
Diese Arbeit stellt deterministische Algorithmen zur Maximierung nicht-monotoner submodularer Funktionen unter Matroid- und Knapsack-Bedingungen vor, die mit Approximationsverhältnissen von bzw. den aktuellen Stand der Technik übertreffen.