91 artigos
Este artigo investiga a complexidade computacional do problema de reconfiguração de conjuntos dominantes de distância- sob as regras de deslizamento e salto de tokens, estabelecendo uma dicotomia de complexidade ao demonstrar que o problema é tratável em tempo polinomial para grafos divididos quando , enquanto permanece PSPACE-completo para outras classes de grafos como planares, bipartidos e cordais.
Este trabalho apresenta um novo método de amostragem com reposição para fluxos de dados que, em uma única passagem sobre uma população de tamanho desconhecido, gera uma amostra ponderada representativa e pronta para uso, com correção e eficiência formalmente provadas e validadas experimentalmente.
Esta carta apresenta uma abordagem inovadora que utiliza acumuladores em cascata para calcular eficientemente somas ponderadas com potências de índice temporal em tempo real, eliminando a necessidade de armazenamento de blocos de dados e reduzindo drasticamente o custo computacional de multiplicações.
Este artigo investiga a complexidade parametrizada do problema do caminho mais curto com restrições disjuntivas positivas, estabelecendo resultados de kernelização e tratabilidade parametrizada fixa para diferentes parâmetros, como o tamanho da solução e propriedades estruturais do grafo de forçamento.
Este artigo apresenta o projeto, análise e desempenho de uma lista de saltos determinística concorrente em nós NUMA de muitos núcleos, avaliando também filas e tabelas hash concorrentes em comparação com a biblioteca TBB da Intel, enquanto propõe estratégias de gerenciamento de memória e uso hierárquico de estruturas de dados para reduzir latências e acessos remotos.
Este artigo demonstra que o problema de Coloração Parcial de Lista Máxima em H é solúvel em tempo polinomial em grafos livres de P₅ para qualquer grafo H fixo, resolvendo uma questão em aberto e melhorando algoritmos anteriores.
Este artigo propõe um mecanismo escalável e baseado no framework Propose-Test-Release (PTR) para a estimação privada do componente principal de grafos sob privacidade diferencial de arestas, alcançando uma precisão superior em grafos "bem-comportados" e uma melhoria de 180 vezes no tempo de execução em comparação com métodos existentes, além de permitir a primeira solução com privacidade diferencial para o problema do subgrafo mais denso.
Este trabalho propõe um novo quadro teórico baseado em formulação matricial para derivar limites superiores e inferiores no Problema de Agendamento de Fluxo de Trabalho Permutacional, demonstrando melhorias significativas nos limites para a maioria das instâncias de benchmark e fornecendo novos insights assintóticos sobre conjecturas de Taillard.
Este artigo apresenta algoritmos clássicos eficientes para os problemas e de Solução Inteira Constrained, demonstrando que não há mais aceleração quântica exponencial para essas instâncias, invalidando assim os resultados anteriores de Chen, Liu e Zhandry.
Este artigo apresenta um novo algoritmo híbrido de programação dinâmica que resolve o problema de dimensionamento de lotes de um único item com desconto de unidades totais de um único ponto de ruptura e preços não decrescentes em tempo , superando a complexidade anterior de .
Este artigo propõe uma nova abordagem algébrica para o Problema de Satisfação de Restrições de Reconfiguração (RCSP), utilizando operações parciais para generalizar resultados de complexidade computacional de domínios booleanos para cenários mais amplos.
Os autores apresentam os primeiros algoritmos de aproximação para duas generalizações do Problema de Atribuição Quadrática Máxima (MaxQAP), especificamente para a versão com restrições de listas e para o problema de -casamento, oferecendo fatores de aproximação que, em casos específicos, igualam o melhor resultado conhecido para o MaxQAP padrão.
Este artigo demonstra que o problema de fluxo de trabalho permutável robusto sob incerteza orçamentada pode ser resolvido em tempo polinomial para duas máquinas e aproximado para um número fixo de máquinas, ao reduzir o problema a múltiplas instâncias do problema nominal por meio de uma técnica de dualização aplicada a uma função objetivo min-max.
Este trabalho propõe algoritmos ótimos de teste de independência que utilizam informações preditivas auxiliares para reduzir a complexidade de amostragem quando as previsões são precisas, mantendo ao mesmo tempo a validade no pior caso e estabelecendo limites inferiores que comprovam a otimalidade do método em cenários bivariados e de alta dimensão.
Este artigo propõe uma abordagem integrativa para a seleção justa de top- que generaliza cenários anteriores para múltiplos grupos protegidos, analisa a complexidade computacional do problema, introduz uma nova medida de disparidade baseada em perda de utilidade para maior estabilidade e apresenta uma solução prática com alto desempenho empírico em conjuntos de dados reais.
Este artigo apresenta a implementação de algoritmos quânticos baseados na busca de Grover para resolver o problema de Coordenação de Sinais de Rede (NSC) e sua versão robusta, demonstrando uma aceleração quadrática na complexidade computacional através de simulações e execução em um computador quântico real.
Este artigo generaliza o modelo de modificação de grafos por escalonamento de discos, permitindo que os discos modificados escolham um raio dentro de um intervalo, e estabelece a complexidade parametrizada do problema para várias classes de grafos, incluindo resultados de FPT para grafos de clusters, solvabilidade polinomial para grafos completos e dureza W[1] para grafos conectados.
Este trabalho desenvolve e valida uma abordagem de decodificação por emparelhamento de grafos para códigos quânticos topológicos bidimensionais invariantes por translação, demonstrando que ela corrige erros significativos, atinge limiares de capacidade não nulos e oferece desempenho comparável a métodos avançados, como o decodificador de propagação de crença com estatísticas ordenadas.
Este artigo resolve uma questão em aberto sobre a complexidade do problema de Correspondência de Morse Ótima em complexos de largura de árvore limitada, apresentando um algoritmo de tempo $2^{O(k \log k)} n$ e provando que essa dependência é ótima sob a Hipótese do Tempo Exponencial (ETH).
Este artigo resolve duas questões em aberto ao provar que encontrar caminhos mais curtos em politopos simples e calcular seu diâmetro são problemas NP-difíceis, enquanto demonstra que é possível encontrar caminhos lineares em tempo polinomial através de formulações estendidas adequadas.