Algoritmos para embalagem de conjunto

Parece haver muito trabalho, para alguns problemas NP-Hard, no desenvolvimento de algoritmos exatos de tempo exponencial rápido (ou seja, resultados da forma: Algoritmo A resolve o problema no tempo O (c ^ n), com c pequeno). Parece haver uma boa quantidade de trabalho nesse sentido para alguns problemas difíceis de NP (por exemplo, Medir e conquistar: um simples algoritmo de conjunto independente de . SODA'06 ), mas eu não capaz de encontrar trabalho semelhante para o problema de embalagem definida. Parece haver um trabalho semelhante em algumas restrições do problema de empacotamento de conjunto (por exemplo, um algoritmo parametrizado para embalagem de 3 conjuntos), mas não encontrei nenhum para o conjunto geral de empacotamento problema. $x$ $O(2^{0.288n})$ $O^{*}(3.523^{k})$

Portanto, minha pergunta é: qual é a melhor complexidade de tempo para solucionar exatamente o problema de empacotamento de conjuntos ponderados, onde existem conjuntos desenhados a partir de um universo de elementos? $m$ $n$

Também estou interessado na relação entre o número de conjuntos e o tamanho do universo. Por exemplo, houve trabalho algorítmico em situações em que é relativamente grande comparado a (isto é, próximo a )? $m$ $n$ $2^n$

ds.algorithms Serviço Travis
fonte

Google ? "definir embalagem"? pt.wikipedia.org/wiki/Set_packing ainda não é uma questão de nível de pesquisa (consulte nossas Perguntas frequentes). Fechando agora ...

Suresh Venkat

@ Suresh, estou interessado nos resultados do formulário: O algoritmo A resolve o problema de empacotamento definido no tempo O (c ^ n), com c pequeno. Existe esse trabalho para outros problemas difíceis de NP (por exemplo, Medir e conquistar: um simples algoritmo de conjunto independente de O (2 ^ 0.288n). SODA'06). O artigo da wikipedia que você vincula não discute isso e não encontrei nenhum artigo recente que discuta a complexidade de tempo do conjunto de embalagens. A maioria dos trabalhos que encontrei é sobre o problema da embalagem do k-set. Esta é uma pergunta do tipo "solicitação de referência". Esse tipo de pergunta é bem-vindo aqui? ou talvez a pergunta não tenha sido escrita suficientemente bem?

Travis Service

Isso faz muito mais sentido, na verdade. o ponto principal é que você está procurando algoritmos EXACT para embalagem de conjunto ponderada. Se você deseja reformular, forneça referências para a embalagem do conjunto

(assim como o que é), ficaria feliz em reabrir - basta sinalizá-lo para atenção do moderador.

k

$k$

precisa

Eu defenderia reabrir esta questão. "Complexidade temporal" geralmente se refere a algoritmos exatos, a menos que seja declarado o contrário, não?

Arnab

Esta questão deve ser reaberta.

quer

De fato, o empacotamento, o particionamento e a cobertura do conjunto foram estudados em termos de tempo exato de execução do algoritmo. Para abordar sua última pergunta, você pode resolver o empacotamento ponderado do conjunto em tempo programando dinamicamente todos os subconjuntos de . Além disso, se seus pesos inteiros estiverem limitados por , você poderá resolvê-lo em , mesmo que seja tão grande quanto , consulte $O(m2^n)$ $[n]$ $M$ $O(M2^n)$ $m$ $2^n$

http://dx.doi.org/10.1137/070683933

BTW, o resultado parametrizado que você lista para conjuntos não é o mais conhecido, consulte $3$

http://arxiv.org/abs/1007.1161

para um algoritmo de última geração e uma lista de resultados anteriores sobre o problema.

Andreas Björklund
fonte

Algoritmos para embalagem de conjunto

Respostas: