cs.DM articles | Gist.Science

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

Cet article démontre la faisabilité de l'encodage par blocs de l'équation de Poisson hétérogène tridimensionnelle pour la simulation des écoulements en réseaux de fractures, montrant que bien que l'encodage séparé de la matrice et du préconditionneur n'améliore pas le nombre de conditionnement effectif, l'algorithme quantique offre une accélération temporelle et des économies de mémoire exponentielles par rapport aux méthodes classiques.

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

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

Cet article présente les premiers algorithmes d'approximation pour deux généralisations du problème d'affectation quadratique maximale, à savoir le problème avec restrictions de listes et le problème de $b$ -appariement, en obtenant des facteurs d'approximation de $O(\sqrt{n}+k)$ et $O(\sqrt{bn})$ respectivement.

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

Robust Permutation Flowshops Under Budgeted Uncertainty

Cet article démontre que le problème d'ordonnancement de flux de permutation robuste sous incertitude budgétisée peut être résolu en temps polynomial pour deux machines et approché pour un nombre fixe de machines, grâce à une réduction ingénieuse vers des instances du problème nominal qui évite la complexité des méthodes heuristiques ou d'optimisation par programmation en nombres entiers.

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

Positional s-of-k games

Cet article introduit le cadre général des jeux de position « s-of-k », où les joueurs marquent des points en s'appropriant une portion de chaque ensemble gagnant, et analyse les scores obtenus sous jeu optimal et sous contrainte de stratégie d'appariement sur diverses grilles régulières.

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

Minimal toughness in subclasses of weakly chordal graphs

Cet article initie l'étude des graphes faiblement chordaux minimalement résilients en classifiant complètement ceux appartenant à plusieurs sous-classes spécifiques, tout en fournissant des preuves simplifiées de résultats antérieurs.

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

Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees

Cet article examine les propriétés structurelles des séquences de flips les plus courtes entre arbres couvrants plans, confirmant certaines conjectures dans des cas spécifiques mais les réfutant dans le cadre général.

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

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

Cet article établit des conditions algébriques nécessaires et suffisantes sur les paramètres d'une règle de cellule automate de premier degré à $d$ états, permettant de vérifier sa réversibilité pour toute taille de réseau en temps constant et de synthétiser toutes les règles réversibles correspondantes.

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

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

Cet article résout la question ouverte sur la dépendance exacte du paramètre de largeur d'arbre pour le problème de l'appariement de Morse optimal en proposant un algorithme en temps $2^{O(k \log k)} n$ et en prouvant, sous l'hypothèse de complexité exponentielle (ETH), qu'aucun algorithme significativement plus rapide n'existe.

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

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

Cet article présente le premier algorithme offrant une amélioration multiplicative par rapport à l'algorithme glouton pour la maximisation d'une fonction sous-modulaire monotone sous une intersection de $k$ contraintes de matroïdes, atteignant un rapport d'approximation de $\frac{2k\ln2}{1+\ln2}+O(\sqrt{k})$ grâce à une approche hybride combinant le glouton et la recherche locale.

Moran Feldman, Justin Ward2026-03-05💻 cs

← Précédent

cs.DM