87 articles
Cet article présente le Huffman-Bucket Sketch (HBS), une structure de données simple et fusionnable qui compresse losslessly un HyperLogLog en bits grâce à un codage de Huffman adaptatif, tout en conservant des temps de mise à jour constants et la fusionnalité.
Cet article présente une procédure linéaire pour reconnaître les sous-ensembles minimalement insatisfaisables de formules 2-CNF, étudie la complexité de leur recherche en distinguant les cas polynomiaux (contenant des clauses unitaires) des cas NP-complets, et propose un algorithme incrémental pour une classe spécifique de ces sous-ensembles.
Cet article présente le sketch Tensor Train à blocs creux (BSTT), une projection aléatoire structurée qui unifie les opérateurs existants et garantit une complexité linéaire par rapport à l'ordre du tenseur et à la dimension du sous-espace, permettant ainsi d'éviter la croissance exponentielle des méthodes précédentes.
Cet article résout une question ouverte en démontrant la première séparation explicite entre la confidentialité différentielle aveugle et adaptative dans le modèle d'observation continue, en présentant un algorithme précis pour le premier cas qui échoue systématiquement dans le second après un nombre constant d'étapes.
Ce papier présente IsalGraph, une méthode qui encode la structure de tout graphe fini simple en une chaîne de caractères compacte et isomorphe-invariante, permettant des applications efficaces en recherche de similarité, génération de graphes et modélisation par langage.
En étendant la méthode des conteneurs, cette étude établit des bornes de complexité d'échantillonnage quasi optimales pour tester la propriété de -clique et la -colorabilité dans le modèle de graphes denses.
Cet article propose un algorithme en ligne 8-compétitif pour la minimisation des coûts dans un modèle de planification de temps occupé sur des machines hétérogènes avec des tâches de longueur uniforme, accompagnée d'une borne inférieure de 2 qui est optimale pour les intervalles non imbriqués.
Cet article présente un algorithme FPT résolvant la question de savoir si un graphe peut être couvert par moins de chemins, en établissant une extension algorithmique du théorème de Gallai-Milgram et en fournissant le premier algorithme polynomial pour le problème du chemin hamiltonien dans les graphes dont le nombre d'indépendance est au plus trois.
Le papier présente -Motif, un algorithme accéléré par GPU qui résout le problème de l'isomorphisme de sous-graphe en reformulant la tâche sous forme d'opérations de base de données tabulaires, permettant ainsi des accélérations allant jusqu'à 595 fois par rapport aux méthodes traditionnelles comme VF2.
Ce papier présente et évalue expérimentalement plusieurs variantes d'arbres B optimisées pour l'indexation efficace sur des dispositifs embarqués à mémoire limitée, démontrant l'avantage significatif des optimisations spécifiques au stockage flash dans le contexte de l'Internet des Objets.
Cet article présente les premiers algorithmes de tri strictement en place et basés sur des comparaisons, dont le temps d'exécution optimal dépend de l'entropie par blocs de l'entrée, en adaptant simplement des algorithmes de fusion naturelle pour des systèmes embarqués à mémoire limitée comme un réfrigérateur.
Ce papier améliore l'analyse de Klivans et al. en démontrant que le degré polynomial nécessaire pour l'apprentissage agnostique de classes de concepts à surface de Gauss bornée est de , établissant ainsi des bornes quasi-optimales pour l'apprentissage des fonctions de seuil polynomial dans le modèle des requêtes statistiques.
Cet article résout une question ouverte en démontrant qu'un algorithme glouton atteint un rapport de compétitivité de $2-2^{1-k}4/3$.
Cet article présente un nouvel algorithme pour reconnaître le rang transversal des hypergraphes et énumérer leurs ensembles de frappe minimaux en améliorant la dépendance temporelle par rapport au nombre d'arêtes, tout en établissant que réduire davantage cette complexité équivaut à résoudre plusieurs problèmes fondamentaux non résolus en algorithmique combinatoire.
Les auteurs prouvent une version affaiblie d'une conjecture récente sur les décompositions arborescentes des graphes excluant certains mineurs induits, en démontrant que de tels graphes admettent une décomposition où chaque sac possède un nombre d'indépendance à distance borné par une fonction polylogarithmique.
Cet article propose une méthode séquentielle pour générer, énumérer et échantillonner des graphes bipartis, dirigés et non orientés à partir de séquences de degrés prescrites, en établissant une condition d'intervalle nécessaire et suffisante pour garantir la faisabilité globale et démontrant une excellente évolutivité sur de grandes instances.
Cet article établit une dichotomie de complexité pour le problème de reconfiguration des ensembles dominants à distance en démontrant qu'il est polynomial sur les graphes split pour (contrairement au cas ), tout en fournissant un algorithme linéaire sur les arbres et en prouvant sa complétude PSPACE sur des graphes planaires et bipartis pour .
Cet article présente un nouvel algorithme de réservoir pondéré avec remise pour les flux de données, capable de générer en une seule passe un échantillon représentatif de taille fixe dont la probabilité d'inclusion est proportionnelle au poids des éléments, tout en garantissant sa correction et son efficacité par rapport aux méthodes existantes.
Cette lettre présente une méthode novatrice utilisant des accumulateurs en cascade pour calculer efficacement des sommes pondérées de puissances d'indices temporels en temps réel, réduisant ainsi le coût multiplicatif de à multiplications constantes tout en éliminant le besoin de stockage de blocs de données.
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.