Venda de blocos de horários

27

Dado intervalos de tempo que k pessoas querem comprar. A pessoa i tem um valor h ( i , j ) 0 para cada intervalo de tempo j . Cada pessoa pode comprar apenas um bloco consecutivo de horários, que podem estar vazios.nkih(i,j)0j

Existe um algoritmo de tempo polinomial para calcular o valor máximo que o vendedor pode alcançar?

Sem a restrição de consecutividade, podemos atribuir cada intervalo de tempo à pessoa que mais o valoriza. Além disso, se fixarmos a ordem dos intervalos de tempo das pessoas, a programação dinâmica poderá ser usada para resolver o valor máximo dos primeiros 0 i k pessoas que compram os primeiros 0 j n intervalos de tempo.k0ik0jn

user11550
fonte

Respostas:

9

Dado um 3CNF com cláusulas nas variáveis x 1 , , x n . Suponha que x i e ¯ x i apareçam na fórmula no máximo k i vezes, respectivamente.ϕ1,,ϕkx1,,xnxixi¯ki

Projetamos um DAG colorido cujos vértices consistem em três partes:G

  • Vértices de "atribuição" e ˉ v i ( j ) , 1 i n , 1 j k i . Cor v i ( j ) com a "cor" x i ( j ) e ˉ v i ( j ) com ¯ x i ( j ) .vi(j)v¯i(j)1in1jkivi(j)xi(j)v¯i(j)xi¯(j)
  • Vértices da "cláusula" , 1 i k , j = 1 , 2 , 3 . Cor w i ( j ) com a cor x i ( j ) (ou ¯ x i ( j ) ) se ¯ x i (ou x i , resp.) For j wi(j)1ikj=1,2,3wi(j)xi(j)xi¯(j)xi¯xij-ésimo literal da cláusula , e é a j cláusula -ésimo contendo este literal.ϕij
  • "Cortar" os vértices . Pinte-os com cores diferentes, diferentes de cima.s=s0,s1,,sn,sn+1,sn+k=t

As arestas incluem:

  • , v i ( j ) v i ( j + 1 ) , v i ( k i ) s i ;si1vi(1)vi(j)vi(j+1)vi(ki)si
  • , ˉ v i ( j ) ˉ v i ( j + 1 ) , ˉ v i ( k i ) s i ;si1v¯i(1)v¯i(j)v¯i(j+1)v¯i(ki)si
  • e , w i ' ( j ' ) s n + i ' .sn+i1wi(j)wi(j)sn+i

Por exemplo, a partir do 3CNF a seguinte gráfico é construído (As direcções de bordo são, da esquerda para a direita). (x1x2x3¯)(x1x2¯x3)insira a descrição da imagem aqui

Agora não é difícil ver que o 3CNF original está satisfeita se e somente se existe um - t caminho com diferentes cores de vértice em G .stG

(A propósito, é um subproduto que a existência de - t path com diferentes cores de vértices no DAG colorido é NP-difícil . Não encontrei muitas literaturas sobre esse problema na perspectiva computacional. Se você sabe, por favor Comente!)stNP-hard

Então, qual é a relação entre o problema de e OP? Intuitivamente, o que vamos fazer é projetar uma matriz h , para que cada cor seja mapeada para uma linha (que é uma pessoa) e as bordas sejam mapeadas para colunas consecutivas (intervalos de tempo). Portanto, um agendamento máximo, que basicamente passa da esquerda para a direita na matriz, corresponde a um caminho s - t .Ghst

Os nossos matriz ter 2 n + 1 + Σ i 2 k i + k colunas, com índices a partir de 0 . No seguinte constrcution X um Y são dois valores satisfazem um « X « Y . As razões X / 1 , Y / X podem ser grandes potências de k e n . Seja K i = 2 i + 2 i jh2n+1+i2ki+k0XY1XYX/1,Y/Xkn.Ki=2i+2j=1iki

  • Para cada , 0 i n , deixe h ( s i , K i ) = h ( s i , K i - k i - 1 ) = h ( s i , K i + k i + 1 + 1 ) = Y (se a coordenada existir, o mesmo abaixo).si0inh(si,Ki)=h(si,Kiki1)=h(si,Ki+ki+1+1)=Y
  • Para cada , seja h ( x i ( j ) , K i - 1 + j ) = X ; Para cada ¯ x i ( j ) , deixá- h ( ¯ x i ( j ) , K i - 1 + k I + 1 + j ) = X .xi(j)h(xi(j),Ki1+j)=Xxi¯(j)h(xi¯(j),Ki1+ki+1+j)=X
  • Para cada , 1 i k e um x literal na cláusula ϕ i ' , seja h ( x , K n + i ' ) = 1 .ϕi1ikxϕih(x,Kn+i)=1
  • Todas as outras entradas são 0.

Por exemplo, para o gráfico de exemplo acima, a matriz correspondente é insira a descrição da imagem aqui

Agora afirmamos: o 3CNF original é satisfatório se e somente se o valor máximo for .(2n+1)Y+ikiX+k

Considere a programação atingindo o valor máximo. Como existem exatamente colunas em h contendo Y , todas elas devem ser cobertas. Para a coluna K i + k i + 1, que tem duas opções de Y , suponha que o planejamento a atribua a s i . Como a coluna K i deve ser atribuída a s i , pela consecutividade, temos que perder as colunas K i + 1 para K i + k(2n+1)hYKi+ki+1YsiKisiKi+1 . O mesmo acontece se o planejamento atribuir a coluna K i + k i + 1 a s i + 1 .Ki+kiKi+ki+1si+1

Portanto, para obter o valor , devemos selecionar todos os demais X disponíveis na matriz, o que corresponde a uma atribuição nas variáveis. Portanto, o valor restante de k é possível se e somente se a atribuição atender a todas as cláusulas.ikiXXk

Como conclusão, decidir o valor máximo de uma programação legal é . Talvez seja por isso que todas as nossas tentativas anteriores de encontrar um algoritmo falharam.NP-hard

Willard Zhan
fonte
Mas, na matriz de exemplo, se eu escolher ¯ x 2 e x 3, ainda assim posso alcançar o objetivo. O que estou fazendo de errado? Além disso, a X em ¯ x 1 ( 1 ) deve ser uma coluna para a direita e o X na ¯ x 1 ( 2 ) deve ser uma coluna para a esquerdax1¯ x2¯x3Xx1¯(1)Xx1¯(2)
rotia
@rotia Sim, e isso significa à esquerda você deve escolher para ter 4 X . Portanto, isso corresponde a uma tarefa satisfatória x 1 = x 2 = 1 , x 3 = 0 . x1,x2,x3¯4Xx1=x2=1,x3=0
Willard Zhan
Você pode esclarecer o que "Suponha um maior nos dois números de aparências dos literais x i e ¯ x i ". significa? Qual é o número de aparência de um literal? Isso é algo sobre o local em que aparece nas cláusulas / fórmula ou quantas vezes aparece na fórmula? É k i um literal ou um número? kixixi¯ki
DW
@DW é um número. Minha expressão não era de fato clara; Eu editei. ki
Willard Zhan
@WillardZhan Sim. Mas se eu escolher essas variáveis, posso obter um valor maior que o da fórmula. Por exemplo, eu defino e X = 7 , de acordo com a fórmula, eu deveria ter apenas 450 pontos (assumindo que k é o número de cláusulas). Mas, escolhendo x 1 , x 2 , ¯ x 3 i pode chegar a 452 pontos, escolhendo os quatro mais à direitaY=60X=7kx1,x2,x3¯
rotia
3

Esta solução tem problemas e será excluída em breve; veja o comentário de templatetypedef.

Você pode resolver isso em tempo polinomial usando fluxo de custo mínimo . A seguir, todas as arestas têm capacidade unitária.

  • Crie um vértice de origem e um vértice de destino t . Enviaremos k unidades de fluxo de s para t .stkst
  • Crie vértices v 0 , , v n para representar os pontos de tempo entre os slots e uma aresta direcionada v j v j + 1 para cada 0 j < n com custo 0.n+1v0,,vnvjvj+10j<n
  • Para cada pessoa , crie o seguinte: i
    • Um vértice da sub-fonte e um vértice da sub-fonte t i .siti
    • Para cada , uma aresta de s i a v j custando Σ j k = 1 h ( i , k ) (que consideramos 0 se j = 0 ).0j<nsivjΣk=1jh(i,k)j=0
    • Para cada , uma aresta de v j a t i custando - Σ j k = 1 h ( i , k ) .1jnvjtiΣk=1jh(i,k)
    • Uma aresta com custo 0.ssi
    • Uma aresta com custo 0.tit

Um fluxo de custo mínimo nessa rede terá um custo total igual ao negativo do melhor lucro possível. (Este custo será negativa, mas isto não é um problema.) Existe uma solução integral óptima em que cada pessoa tem uma única aresta deixando s i com um fluxo de 1 e uma aresta única chegada no t i com um fluxo de 1 , e todas as outras arestas incidentes em s i ou t eu tenho 0 fluxo. Deixe estas flow-1 bordas para pessoa i ser s i v j e v k t i : então k jisitisitiisivjvktikj, já que os únicos caminhos entre os vértices são aqueles que aumentam o índice. Se k = j , a pessoa i não recebe nenhum horário; caso contrário, a pessoa i recebe o bloco de intervalos de tempo j + 1 , , k .vk=jiij+1,,k

Intuitivamente, cada pessoa "recebe" 1 unidade de fluxo de e escolhe um horário de início (limite) e um tempo final (limite); essas arestas inicial e final são as únicas arestas com custo diferente de zero na rede e podemos representar o valor de um bloco j + 1 , , k como a diferença de duas somas de prefixo. As capacidades da unidade nas bordas entre os v- vtices atuam para impedir que 2 pessoas usem o mesmo intervalo de tempo.sj+1,,kv

Curiosamente, essa formulação funcionará mesmo que os valores possam ser negativos.h(i,j)

j_random_hacker
fonte
3
Isso pode falhar se alguma pessoa leva uma rota de sua fonte de pia de outra pessoa e vice-versa? i
Templatetypedef
@templatetypedef: Eu acredito que você está certo; Excluirei esta resposta em breve. Em vez disso, e quanto a essa construção: temos os mesmos vértices e arestas de antes, mas agora tentamos "encadear" uma única unidade de fluxo através de um "pipeline" de pessoas (ordenado pelo aumento do valor de ) excluindo todas as arestas s s i exceto s s 1 e todas as arestas t i t, exceto t k t , e adicionando uma aresta t i s i + 1 com enorme custo negativo - M para cada 1 i < kississ1tittkttisi+1M1i<k. O s forçará a única unidade de fluxo a visitar todos os k - 1 dessas bordas da "tubulação" em qualquer solução ideal. Mk1
Jrandom_hacker
@j_random_hacker, você está forçando uma ordem do pessoas. k
Chao Xu
@ChaoXu: Acho que não: em qualquer atribuição de blocos a pessoas, a tarefa pode ser listada em ordem crescente por pessoa. (Note-se que nada impede uma pessoa sendo atribuído um bloco terminando em j ' < j , onde j é o primeiro bloco atribuído a pessoa i .) Mas eu tenho a sensação de que um parente próximo do problema que afetou o meu primeiro tentar também afeta este ...i>ij<jji
j_random_hacker
@j_random_hacker O custo de exigiria que s i para ser o i th pessoa na solução óptima. sivjsii
Chao Xu