91 Arbeiten
Dieser Artikel untersucht die Komplexität des Rekonfigurationsproblems für Distanz--Dominanzmengen und zeigt eine interessante Komplexitätsdichotomie auf, indem er für auf Split-Graphen polynomielle Algorithmen nachweist, während das Problem auf planaren Graphen mit maximalem Grad drei sowie auf bipartiten und chordalen Graphen weiterhin PSPACE-vollständig bleibt.
Diese Arbeit stellt einen effizienten, einpassigen Algorithmus vor, der gewichtete Stichproben mit Zurücklegen aus Datenströmen unbekannter Größe generiert und dabei die Korrektheit sowie die direkte Nutzbarkeit der laufenden Stichprobe formal nachweist.
Dieser Brief stellt eine neuartige Methode vor, die mithilfe kaskadierter Akkumulatoren zeitindexierte gewichtete Summen der Form ohne vollständige Datenspeicherung und mit nur Multiplikationen effizient berechnet, was eine Echtzeitverarbeitung ermöglicht.
Diese Arbeit untersucht die parametrisierte Komplexität des kürzesten Pfadproblems mit positiven disjunktiven Einschränkungen und liefert Kernelisierungen sowie Fixed-Parameter-Tractability-Ergebnisse für verschiedene Parameter wie die Lösunggröße und strukturelle Eigenschaften des Zwangsgraphen.
Diese Arbeit stellt den Entwurf, die Analyse und die Leistung eines deterministischen, nebenläufigen Skiplists auf vielen NUMA-Kernen vor, bewertet weitere nebenläufige Datenstrukturen im Vergleich zu Intels TBB-Bibliothek und schlägt Strategien für das Speichermanagement sowie eine hierarchische Nutzung dieser Strukturen vor, um Speicherlatenzen durch die Reduzierung von Zugriffen auf entfernte NUMA-Knoten zu verringern.
Dieser Artikel zeigt, dass das Maximum Partial List H-Coloring-Problem auf P_5-freien Graphen für jeden festen Graphen H in polynomialer Zeit lösbar ist, wodurch eine offene Frage von Agrawal et al. beantwortet und ein bestehender Algorithmus von Chudnovsky et al. verbessert wird.
Die Autoren stellen einen skalierbaren, differenziell privaten Algorithmus vor, der auf dem Propose-Test-Release-Framework basiert und durch die Ausnutzung instanzspezifischer Sensitivitäten eine hohe Genauigkeit bei der Schätzung des Netzwerkhauptkomponenten sowie eine 180-fache Laufzeitverbesserung gegenüber bestehenden Methoden ermöglicht.
Diese Arbeit stellt ein neues Rahmenwerk zur Berechnung von Schranken für das Permutations-Fließshop-Scheduling-Problem vor, das auf einer Matrixformulierung basiert und durch die effiziente Lösung von Min-Max-Ausdrücken über Pfadmengen signifikante Verbesserungen bei den unteren und oberen Schranken für Standard-Testinstanzen sowie neue asymptotische Erkenntnisse liefert.
Diese Arbeit widerlegt die Annahme einer exponentiellen Quantenbeschleunigung für das -Problem, indem sie effiziente klassische Algorithmen für alle in der Studie von Chen, Liu und Zhandry behandelten Instanzen vorstellt.
Diese Arbeit stellt einen neuartigen hybriden dynamischen Programmieralgorithmus vor, der das Losgrößenproblem mit einem einzigen All-Units-Rabatt und nicht-steigenden Preisen in Zeit löst und damit den bisherigen -Algorithmus verbessert.
Dieser Artikel stellt einen neuartigen algebraischen Ansatz für das Rekonfigurations-CSP vor, der partielle Operationen nutzt, um Komplexitätsresultate von booleschen Domänen auf allgemeinere Settings zu erweitern und dabei insbesondere die Umkonfiguration von Graphhomomorphismen zu behandeln.
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.
Diese Arbeit stellt robuste, vorhersagegestützte Algorithmen für den Unabhängigkeitstest vor, die im worst-case ihre Gültigkeit bewahren, aber bei genauen Vorhersagen die Stichprobenkomplexität signifikant reduzieren und dabei optimale untere Schranken erreichen.
Diese Arbeit stellt einen integrativen Ansatz zur Verallgemeinerung der fairen Top--Auswahl auf mehrere geschützte Gruppen vor, der durch eine neue Härteanalyse die Berechnungskomplexität aufdeckt, eine alternative Disparitätsmessung über den Nutzenverlust einführt und durch eine zweigleisige Lösung sowohl theoretische Erkenntnisse als auch starke empirische Ergebnisse auf realen Datensätzen liefert.
Diese Arbeit stellt Quantenalgorithmen vor, die das NP-vollständige Problem der Netzwerksignal-Koordination sowie dessen robuste Variante mittels Grovers Suchalgorithmus lösen und dabei eine quadratische Beschleunigung gegenüber klassischen Ansätzen erreichen, was durch Simulationen und Tests auf einem echten Quantencomputer verifiziert wurde.
Diese Arbeit verallgemeinert das Modell der Graphmodifikation durch Disk-Skalierung von einem festen Radius auf einen Intervall-basierten Radiusbereich und untersucht die parametrisierte Komplexität dieses Problems für verschiedene Graphklassen, wobei sie sowohl neue FPT- und Polynomzeit-Ergebnisse als auch W[1]-Härte bewahrt und offene Fragen aus der vorherigen Forschung beantwortet.
In dieser Arbeit wird ein Graph-Matching-Decodierungsansatz für allgemeine zweidimensionale topologische translationsinvariante Quantencodes entwickelt, der durch eine Vergröberung des Syndroms auf Toric-Code-Anregungen nicht nur beweisbare Fehlerkorrektur bis zu einem konstanten Bruchteil des Codesabstands und nicht-null Kapazitätsschwellenwerte garantiert, sondern auch für bivariate Bicycle-Codes eine Leistung aufweist, die mit dem belief-propagation-with-ordered-statistics-Decoder vergleichbar ist.
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 beweist, dass die Berechnung kürzester monotoner Pfade auf einfachen Polytopen sowie der Durchmesser solcher Polytope NP-schwer sind, während sie gleichzeitig zeigt, dass für jede Polytop eine kleine, einfache erweiterte Formulierung existiert, in der kürzeste Pfade in polynomieller Zeit gefunden werden können.