88 articles
Cet article étudie la complexité paramétrée du problème du plus court chemin avec des contraintes disjonctives positives, en établissant des noyaux de taille polynomiale et des résultats de tractabilité paramétrée selon la taille de la solution et les propriétés structurelles du graphe de contraintes.
Cet article présente la conception, l'analyse et les performances d'une liste sautante déterministe concurrente sur des nœuds NUMA many-core, tout en évaluant des implémentations de files d'attente et de tables de hachage concurrentes comparées à la bibliothèque Intel TBB, et propose des stratégies de gestion de la mémoire et une utilisation hiérarchique des structures de données pour réduire les défauts de page, les ratés de cache et les accès mémoire distants.
Cet article démontre que le problème de coloration partielle maximale avec listes sur les graphes sans est soluble en temps polynomial pour tout graphe fixé, résolvant ainsi une question ouverte et améliorant les algorithmes précédents.
Cet article propose un cadre Propose-Test-Release (PTR) scalable et différentiellement privé pour estimer efficacement la composante principale d'un graphe, offrant une précision supérieure et une accélération de 180 fois par rapport aux méthodes existantes sur de grands réseaux réels.
Cet article propose un nouveau cadre théorique basé sur une formulation matricielle pour établir des bornes supérieures et inférieures sur le problème d'ordonnancement en atelier de type flowshop, démontrant par des tests sur les benchmarks Taillard et VRF une amélioration significative de ces bornes ainsi que des avancées théoriques sur les conjectures de Taillard et les ratios d'approximation asymptotiques.
Cet article présente des algorithmes classiques efficaces pour les problèmes et à solutions entières contraintes, réfutant ainsi l'existence d'une accélération quantique exponentielle pour ces problèmes.
Cet article propose un nouvel algorithme hybride de programmation dynamique résolvant le problème de dimensionnement de lots pour un article unique avec une remise all-units à un point de rupture et des prix non croissants en temps , améliorant ainsi la complexité précédente de .
Cet article propose une nouvelle approche algébrique du problème de reconfiguration CSP (RCSP) fondée sur des opérations partielles, permettant d'étendre les résultats de complexité du domaine booléen à des cadres plus généraux et d'identifier de nouvelles instances traitables.
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 -appariement, en obtenant des facteurs d'approximation de et respectivement.
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.
Cet article propose des algorithmes optimaux pour tester l'indépendance de distributions en intégrant des informations prédictives auxiliaires, garantissant une validité robuste dans le pire des cas tout en améliorant significativement l'efficacité de l'échantillonnage lorsque ces prédictions sont précises.
Cet article propose une approche intégrative pour généraliser la sélection équitable top- à plusieurs groupes protégés en minimisant la disparité par rapport à une fonction de référence, en analysant la complexité computationnelle du problème et en introduisant une nouvelle mesure de perte d'utilité pour améliorer la stabilité des résultats sur des données réelles.
Cet article présente la mise en œuvre et l'analyse de complexité d'algorithmes quantiques basés sur la recherche de Grover pour résoudre le problème NP-complet de coordination des signaux réseau, y compris une formulation robuste offrant une accélération quadratique indépendante de la taille de l'espace de recherche.
Cet article généralise le modèle de modification de graphes par mise à l'échelle de disques en permettant un choix de rayon dans un intervalle, établissant ainsi la complexité paramétrée de ce problème pour diverses classes de graphes et répondant à des questions ouvertes posées par Fomin et al.
Cet article propose et valide une approche de décodage par appariement de graphes pour les codes quantiques topologiques invariants par translation en deux dimensions, démontrant qu'elle atteint des seuils de capacité non nuls et offre des performances comparables aux méthodes avancées pour les codes de type bivariate bicycle.
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.
Cet article résout deux problèmes ouverts majeurs en démontrant que le calcul du plus court chemin monotone sur un polytope simple et celui du diamètre d'un tel polytope sont des problèmes NP-difficiles, tout en proposant une formulation étendue permettant de trouver un chemin linéaire entre deux sommets en temps polynomial.
Cet article présente une structure de données entièrement dynamique qui maintient un sparsificateur spectral d'un graphe géométrique sous des mises à jour de points avec un temps de mise à jour quasi-linéaire, tout en étant robuste face à des adversaires adaptatifs et en permettant des opérations matricielles rapides via un sketch randomisé.
Cet article propose une approche novatrice et symétrique pour résoudre les jeux à paiement actualisé en minimisant la somme des erreurs d'inéquations via une amélioration objective itérative, défiant ainsi la dichotomie traditionnelle entre l'amélioration de stratégie et l'itération de valeur.
Cet article établit que la détection de la corrélation entre deux graphes stochastiques en blocs subsampelés est possible par des polynômes de bas degré si et seulement si le taux d'échantillonnage dépasse le minimum entre la constante d'Otter et le seuil de Kesten-Stigum, définissant ainsi la frontière entre les régimes facile et difficile pour ce problème.