91 papers
Dit artikel onderzoekt de complexiteit van het herschikingsprobleem voor afstand- dominante verzamelingen, waarbij het een interessante dichotomie aantoont door aan te tonen dat het probleem op splitgrafen voor in ligt, terwijl het op andere graafklassen zoals planaire en bipartiete grafen -volledig blijft.
Dit artikel presenteert een nieuwe, efficiënte methode voor gewogen reservoirsampling met vervanging van datastromen die in één doorloop een representatieve steekproef genereert zonder post-processing, waarvan de correctheid formeel is bewezen en de prestaties experimenteel zijn gevalideerd.
Dit artikel introduceert een nieuwe methode met gekaskadeerde accumulatoren om tijdsindex-gemachtigde gewogen sommen efficiënt te berekenen door de vermenigvuldigingskosten te reduceren tot slechts constante vermenigvuldigingen, waardoor opslag van volledige datablokken wordt vermeden en real-time verwerking mogelijk wordt.
Dit artikel onderzoekt de parameteriseringscomplexiteit van het kortste-padprobleem met positieve disjunctieve constraints en levert kerningresultaten met of vertices voor de oplossingsgrootte , evenals vast-parameter-tractabiliteitsresultaten voor structurele parameters van de dwanggraaf.
Dit artikel presenteert het ontwerp, de analyse en de prestaties van een concurrerende deterministische skiplist voor many-core NUMA-nodes, vergeleken met andere lock-free datastructuren en Intel TBB, en introduceert strategieën voor geheugenbeheer en hiërarchisch gebruik om cache-misses en remote NUMA-toegang te verminderen.
Dit artikel bewijst dat het Maximum Partial List H-Coloring-probleem voor elke vaste graaf H in polynomiale tijd oplosbaar is op P5-vrije grafen, waarmee een open vraag van Agrawal et al. wordt beantwoord en een bestaand algoritme wordt verbeterd.
Deze paper introduceert een schaalbaar en differentieel privé algoritme dat het Propose-Test-Release-framework toepast om de hoofdcomponent van een netwerk met hoge nauwkeurigheid te schatten, waardoor een tot nu toe onopgelost probleem van de Dichtste--subgraaf wordt opgelost en een 180-voudige versnelling in rekentijd wordt bereikt ten opzichte van bestaande methoden.
Dit artikel introduceert een nieuw theoretisch raamwerk voor het afleiden van boven- en ondergrenzen voor het permutatie-flowshop-planningsprobleem, dat via een polynoomtijd-oplosbare min-max-formulering aanzienlijk betere resultaten oplevert op standaardbenchmarks en nieuwe inzichten biedt in asymptotische eigenschappen en een conjectuur van Taillard.
Deze paper presenteert efficiënte klassieke algoritmen voor het -probleem en verwante varianten, waarmee wordt aangetoond dat er geen exponentiële kwantumsnelheidswinst meer bestaat voor deze eerder als kwantum-veelbelovend beschouwde problemen.
Dit artikel presenteert een hybride dynamisch programmeringsalgoritme met een tijdscomplexiteit van voor het single-item lot-sizingprobleem met een 1-breakpoint all-units-korting en niet-stijgende prijzen, wat een verbetering is ten opzichte van de eerdere -oplossing.
Dit artikel introduceert een nieuwe algebraïsche aanpak voor het Reconfiguration CSP-probleem die, in tegenstelling tot traditionele methoden, gebruikmaakt van partiële operaties om complexiteitsresultaten van Booleaanse domeinen uit te breiden naar bredere contexten.
Dit artikel introduceert de eerste benaderingsalgoritmen voor twee generalisaties van het Maximum Quadratic Assignment Problem, namelijk de lijst-beperkte variant en de -matching variant, met respectievelijk een - en een -benadering die asymptotisch aansluiten bij de beste bekende resultaten voor het standaardprobleem.
Dit artikel toont aan dat het robuuste permutatie-flowshop-probleem onder budgettair onzekerheidsmodel in polynomiale tijd kan worden opgelost voor twee machines en benaderd voor een vast aantal machines, door het probleem te reduceren tot het oplossen van een polynomiaal aantal instanties van het nominale probleem.
Dit artikel introduceert robuuste algoritmen voor het testen van onafhankelijkheid van verdelingen die, door gebruik te maken van voorspellende informatie, de steekproefgrootte aanzienlijk verminderen wanneer de voorspelling accuraat is, terwijl ze hun geldigheid in het ergste geval behouden en optimale sample-complexiteit bereiken.
Dit paper introduceert een geïntegreerde aanpak voor het selecteren van eerlijke top- kandidaten over meerdere beschermde groepen, waarbij zowel de hardheid van het probleem wordt geanalyseerd als een nieuwe maatstaf voor utiliteitsverlies wordt voorgesteld om robuustere en efficiëntere oplossingen te garanderen.
Dit artikel presenteert de ontwikkeling en simulatie van kwantumalgoritmen, gebaseerd op Grover's zoekalgoritme, die een kwadratische versnelling bieden voor het oplossen van het NP-volledige Netwerksignaalcoördinatieprobleem en zijn robuuste varianten, zelfs bij polynoom-precisie.
Dit artikel generaliseert het bestaande model van grafmodificatie via schijfschaling door de straal binnen een interval te laten variëren in plaats van vast te staan, en analyseert de parameteriseerde complexiteit van dit probleem voor verschillende grafklassen, waarbij zowel nieuwe algoritmen als hardheidsresultaten worden bewezen die eerdere open vragen beantwoorden.
Deze paper introduceert een grafische matching-decoder voor tweedimensionale topologische translatie-invariante codes die, door het code te coarsen naar een effectieve beschrijving in termen van torische code-excitaties, bewezen correcte fouten tot een constant deel van de code-afstand en numeriek vergelijkbare prestaties levert met geavanceerde decoders voor bivariate bicycle-codes.
Deze paper presenteert een nieuw algoritme met looptijd $2^{O(k \log k)} nk$, en bewijst dat deze complexiteit scherp is onder de Exponentiële Tijd Hypothese.
Deze paper bewijst dat het vinden van de kortste paden op eenvoudige polytopen en het berekenen van hun diameter NP-hard is, terwijl er tegelijkertijd wordt aangetoond dat voor elke polytoop een uitgebreide formulering bestaat waarlangs kortste paden in polynomiale tijd kunnen worden gevonden.