cs.DM articoli | Gist.Science

Block encoding the 3D heterogeneous Poisson equation with application to fracture flow

Questo studio dimostra che, sebbene l'incodifica a blocchi di un sistema di equazioni di Poisson 3D eterogenee permetta un algoritmo quantistico con complessità temporale e memoria superiori ai metodi classici, l'incapacità di migliorare il numero di condizione efficace tramite la precondizionazione separata rappresenta una limitazione significativa per l'applicazione pratica di tali algoritmi nella simulazione del flusso di fratture geologiche.

Austin Pechan, John Golden, Daniel O'Malley2026-03-06⚛️ quant-ph

Approximation Algorithms for the $b$ -Matching and List-Restricted Variants of MaxQAP

Il paper presenta i primi algoritmi di approssimazione per due generalizzazioni del Maximum Quadratic Assignment Problem, fornendo un fattore di approssimazione $O(\sqrt{n}+k)$ per il problema con liste vincolate e $O(\sqrt{bn})$ per il problema di $b$ -matching, entrambi basati su rilassamenti di programmazione lineare e arrotondamento randomizzato.

Jiratchaphat Nanta, Vorapong Suppakitpaisarn, Piyashat Sripratak2026-03-06💻 cs

Robust Permutation Flowshops Under Budgeted Uncertainty

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.

Noam Goldberg, Danny Hermelin, Dvir Shabtay2026-03-06🔢 math

Positional s-of-k games

Questo lavoro introduce il framework generale dei giochi "s-of-k", che estendono i giochi posizionali Maker-Breaker consentendo di segnare punti reclamando una porzione s di un insieme vincente di dimensione k, analizzando sia il punteggio ottimale (SC) che quello vincolato a strategie di accoppiamento (SC₂) su varie griglie regolari.

Eric Duchêne, Valentin Gledel, Miloš Stojaković2026-03-06🔢 math

Minimal toughness in subclasses of weakly chordal graphs

Questo studio classifica completamente i grafi minimamente duri in diverse sottoclassi di grafi debolmente cordali, fornendo al contempo dimostrazioni semplificate di risultati precedenti e avviando l'analisi di questa proprietà nella classe più ampia dei grafi debolmente cordali.

J. Pascal Gollin, Martin Milanič, Laura Ogrin2026-03-06🔢 math

Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees

Questo studio analizza le proprietà strutturali delle sequenze di flip più brevi tra alberi spazianti piani in posizione convessa, confermando o smentendo diverse congetture recenti sulla loro natura e sui limiti del numero di volte in cui un'arista può essere ribaltata.

Oswin Aichholzer, Joseph Dorfer, Peter Kramer + 2 more2026-03-06💻 cs

Algebraic Characterization of Reversible First Degree Cellular Automata over $\mathbb{Z}_d$

Questo articolo presenta condizioni algebriche necessarie e sufficienti, verificabili in tempo costante, per garantire la reversibilità di automi cellulari di primo grado a $d$ stati su reticoli finiti di qualsiasi dimensione.

Baby C. J., Kamalika Bhattacharjee2026-03-06💻 cs

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes

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)} n $parametrizzato per la larghezza ad albero$ k$ e dimostrando che tale dipendenza è ottimale sotto l'Ipotesi del Tempo Esponenziale (ETH).

Geevarghese Philip, Erlend Raa Vågset2026-03-06🔢 math

Submodular Maximization over a Matroid $k$ -Intersection: Multiplicative Improvement over Greedy

Questo lavoro presenta il primo miglioramento moltiplicativo rispetto all'algoritmo greedy per la massimizzazione di funzioni submodulari non negative e monotone soggette all'intersezione di $k$ matroidi, ottenendo un rapporto di approssimazione inferiore a $0.819k $tramite un approccio ibrido greedy-local search che funziona in tempo polinomiale indipendente da$ k$.

Moran Feldman, Justin Ward2026-03-05💻 cs

← Precedente

cs.DM