91 articoli
Il documento stabilisce una dicotomia di complessità per il problema di riconfigurazione dell'insieme dominante a distanza- (), dimostrando che è risolvibile in tempo polinomiale sui grafi split (con un algoritmo lineare sugli alberi sotto la regola ) mentre rimane -completo su grafi planari, bipartiti e cordali, estendendo così i risultati noti per il caso .
Questo lavoro presenta un nuovo metodo di campionamento casuale con sostituzione per flussi di dati ponderati, che genera in un'unica passata un campione rappresentativo senza richiedere post-elaborazione, dimostrando formalmente la sua correttezza ed efficienza rispetto agli approcci esistenti.
Questa lettera presenta un nuovo approccio basato su accumulatori in cascata per calcolare in modo efficiente somme pesate con potenze dell'indice temporale, riducendo drasticamente il costo computazionale e l'uso di memoria rispetto ai metodi tradizionali.
Questo articolo studia la complessità parametrizzata del problema del cammino minimo con vincoli disgiuntivi positivi, fornendo kernelizzazioni polinomiali basate sulla dimensione della soluzione e risultati di trattabilità parametrizzata basati sulle proprietà strutturali del grafo dei vincoli.
Questo articolo presenta la progettazione, l'analisi e le prestazioni di una skip list deterministica concorrente su nodi NUMA many-core, valutando inoltre code senza lock e tabelle hash concorrenti confrontate con la libreria Intel TBB, mentre introduce strategie di gestione della memoria e un uso gerarchico delle strutture dati per ridurre i fault di pagina, i miss nella cache e le latenze di accesso alla memoria remota.
Questo articolo dimostra che il problema del Maximum Partial List H-Coloring è risolvibile in tempo polinomiale sui grafi privi di P_5 per ogni grafo H fissato, risolvendo una questione aperta e migliorando un precedente algoritmo a tempo esponenziale.
Il paper propone un nuovo framework Differentially Private basato su Propose-Test-Release che, garantendo la privacy per tutti i dataset, offre un'estimazione scalabile e ad alta accuratezza della componente principale di grafi reali, superando i limiti di complessità e precisione degli algoritmi esistenti e abilitando per la prima volta la risoluzione privata del problema del Densest-k-subgraph.
Questo lavoro presenta un nuovo quadro teorico basato su una formulazione matriciale per derivare limiti superiori e inferiori risolvibili in tempo polinomiale per il problema di scheduling flowshop permutazionale, dimostrando miglioramenti significativi sui benchmark Taillard e VRF e fornendo nuovi risultati asintotici che avanzano la comprensione dei limiti di qualità esistenti.
Questo lavoro presenta algoritmi classici efficienti per i problemi e a soluzione intera vincolata, dimostrando che non esiste più un vantaggio quantistico esponenziale per tali problemi, invalidando così i risultati precedenti di Chen, Liu e Zhandry.
Questo articolo presenta un nuovo algoritmo ibrido a complessità temporale che risolve il problema di dimensionamento dei lotti per un singolo articolo con sconti all'unità a un punto di rottura e prezzi non crescenti, migliorando significativamente la complessità rispetto al precedente stato dell'arte di .
Questo articolo propone un nuovo approccio algebrico basato su operazioni parziali per analizzare la complessità computazionale del problema di riconfigurazione CSP, estendendo i risultati noti dai domini booleani a contesti più generali.
Il paper presenta i primi algoritmi di approssimazione per due generalizzazioni del Maximum Quadratic Assignment Problem, fornendo un fattore di approssimazione per il problema con liste vincolate e per il problema di -matching, entrambi basati su rilassamenti di programmazione lineare e arrotondamento randomizzato.
Questo articolo dimostra che il problema del flusso di lavoro permutazionale robusto sotto incertezza budgetizzata può essere risolto in tempo polinomiale per due macchine e approssimato per un numero fisso di macchine, riducendo il problema a un numero polinomiale di istanze del problema nominale tramite una tecnica di dualizzazione applicata a un obiettivo min-max.
Questo lavoro propone algoritmi ottimali per il test di indipendenza delle distribuzioni che, integrando informazioni predittive ausiliarie, garantiscono validità nel caso peggiore e migliorano significativamente l'efficienza del campionamento quando le previsioni sono accurate, estendendo il risultato al caso multivariato e fornendo limiti inferiori minimax corrispondenti.
Questo lavoro generalizza la selezione top- equa a più gruppi protetti, analizzandone la complessità computazionale e proponendo una soluzione pratica che bilancia l'efficienza, la minimizzazione della disparità rispetto a una funzione di riferimento e la stabilità della funzione di punteggio rispetto alle perturbazioni.
Questo lavoro presenta l'implementazione e la simulazione di algoritmi quantistici basati sulla ricerca di Grover per risolvere il problema NP-completo di coordinazione dei segnali di rete e la sua variante robusta, dimostrandone il vantaggio quadratico sia in simulazione che su un computer quantistico reale.
Questo lavoro generalizza il modello di scalatura dei dischi consentendo di scegliere un raggio all'interno di un intervallo, dimostrando che il problema è in XP per classi di grafi riconoscibili in tempo polinomiale e fornendo risultati di complessità specifici (inclusi NP-difficile, FPT e W[1]-duro) per diverse classi di grafi, risolvendo così alcune domande aperte poste da Fomin et al.
Questo lavoro propone un approccio basato sul matching grafico per decodificare codici quantistici topologici bidimensionali invarianti per traslazione, dimostrando che tale metodo garantisce soglie di tolleranza agli errori non nulle e prestazioni competitive, rendendolo una soluzione praticabile anche per i codici bivariate bicycle.
Questo lavoro risolve una questione aperta sulla complessità del problema della corrispondenza di Morse ottimale su complessi CW regolari, presentando un algoritmo con tempo di esecuzione $2^{O(k \log k)} nk$ e dimostrando che tale dipendenza è ottimale sotto l'Ipotesi del Tempo Esponenziale (ETH).
Questo articolo risolve due problemi aperti dimostrando che il calcolo del percorso più breve su polipoli semplici e il diametro di tali polipoli sono problemi NP-difficili, pur mostrando l'esistenza di formulazioni estese che permettono di trovare percorsi lineari in tempo polinomiale.