48 artigos
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 artigo apresenta um quadro geral para jogos posicionais de pontuação chamados "s-of-k", onde os jogadores marcam pontos ao reivindicar pelo menos 's' elementos de um conjunto vencedor de tamanho 'k', investigando as pontuações alcançáveis sob jogada ótima e sob restrições de estratégias de emparelhamento em diversas grades regulares.
Este artigo inicia o estudo de grafos minimamente duros na classe dos grafos fracamente cordais, fornecendo classificações completas para várias subclasses e oferecendo provas simplificadas de resultados anteriores sobre o tema.
Este artigo investiga as propriedades estruturais das sequências de flips mais curtas entre árvores geradoras planas em posições convexas, confirmando e refutando conjecturas recentes sobre a restrição de arestas utilizadas e o número máximo de vezes que uma aresta pode ser invertida.
Este artigo caracteriza algebricamente a reversibilidade de autômatos celulares de primeiro grau sobre , estabelecendo três condições necessárias e suficientes que permitem verificar a reversibilidade global de qualquer regra desse tipo em tempo constante, independentemente do tamanho da rede.
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 apresenta o primeiro algoritmo que oferece uma melhoria multiplicativa sobre a razão de aproximação do algoritmo ganancioso para a maximização de funções submodulares sob interseção de matróides, alcançando uma razão de aproximadamente $0,819kk$ e aplicável também a casos não monotônicos e a restrições de paridade.