Complexidade do problema da cobertura do intervalo

17

Considere o seguinte problemaQ : Estamos dado um número inteiro , e intervalos com . Também recebemos números inteiros . A tarefa é selecionar um número mínimo de intervalos para que para cada , pelo menos intervalos contendo o número inteiro sejam selecionados.k [ l i , r i ] 1 l ir i2 n 2 n d 1 , ... , d 2 n0 [ l i , r i ] i = 1 , ... , 2 n d i ink[li,ri]1 1euEurEu2n2nd1 1,...,d2n0 0[euEu,rEu]Eu=1 1,...,2ndEuEu

Não é difícil ver que pode ser resolvido em tempo polinomial (veja abaixo).Q

Agora considere o seguinte problemaQ ligeiramente modificado : A entrada do problema é a mesma de antes. No entanto, a tarefa agora é selecionar um número mínimo de intervalos para que, para cada , pelo menos d_ {2i-1} intervalos contendo o número inteiro 2i-1 ou pelo menos d_ {2i} intervalos contendo o o número inteiro 2i é selecionado (com “ou” queremos dizer o usual lógico ou).d 2 i - 1 2 i - 1 d 2 i 2 iEu=1 1,...,nd2Eu-1 12Eu-1 1d2Eu2Eu

Minha pergunta: Q ' pode Qser resolvido em tempo polinomial?

Aqui estão duas maneiras de resolver o Q eficiência:

Um algoritmo simples e ganancioso: varra os intervalos da esquerda para a direita e selecione apenas os intervalos necessários para “satisfazer” os números . Sempre que houver uma escolha entre diferentes intervalos, escolha aquele (s) com o ponto final direito máximo.dEu

Um programa inteiro: para cada intervalo introduza uma variável de decisão com x_i = 1 se o intervalo for selecionado. O objetivo é minimizar x_1 +… + x_k , sujeito às restrições \ sum_ {j: i \ in [l_j, r_j]} x_j \ geq d_i . A matriz de restrição deste programa inteiro possui as propriedades consecutivas e, portanto, o relaxamento linear da programação deste programa tem uma solução ótima inteira.[euEu,rEu]xEu{0 0,1 1}xEu=1 1x1 1+...+xkj:Eu[euj,rj]xjdEu

Obrigado por qualquer dica, e também por referências!

Torsten Mütze
fonte

Respostas:

-1

Cada instância de Q pode ser transformada em uma instância do Problema de cobertura de conjuntos múltiplos, onde os locais são os intervalos , cobrindo uma sequência consecutiva de pontos de demanda (= números inteiros ).[euEu,rEu]dEu

Benjamin
fonte
3
Você pode melhorar a resposta adicionando a definição de Problema de Tampa de Conjunto Múltiplo (MSCP) e mais detalhes sobre a redução? Em particular, um exemplo de MSCP (pelo menos a "versão" Sei) é um gráfico bipartido e só V 1 é uma união de conjuntos disjuntos; de que maneira a redução mapeia as arestas de V 1 a V 2 ? G=(V1 1,V2,E)V1 1V1 1V2
Marzio De Biasi