Venda de blocos de horários

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

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 pessoas que compram os primeiros intervalos de tempo. $k$ $0\le i \le k$ $0\le j \le n$

algorithms optimization np-hard scheduling user11550
fonte

Respostas:

Dado um 3CNF com cláusulas nas variáveis . Suponha que e apareçam na fórmula no máximo vezes, respectivamente. $\phi_1,\ldots,\phi_k$ $x_1,\ldots,x_n$ $x_i$ $\overline{x_i}$ $k_i$

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

"atribuição" e , , . Cor com a "cor" e com . $v_i(j)$ $\bar{v}_i(j)$ $1\leq i\leq n$ $1\leq j\leq k_i$ $v_i(j)$ $x_i(j)$ $\bar{v}_i(j)$ $\overline{x_i}(j)$
Vértices da "cláusula" , , . Cor com a cor (ou ) se (ou , resp.) For $w_{i'}(j')$ $1\leq i'\leq k$ $j'=1,2,3$ $w_{i'}(j')$ $x_i(j)$ $\overline{x_i}(j)$ $\overline{x_i}$ $x_i$ $j'$ -ésimo literal da cláusula , e é a cláusula -ésimo contendo este literal. $\phi_{i'}$ $j$
"Cortar" os vértices . Pinte-os com cores diferentes, diferentes de cima. $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$

As arestas incluem:

, , ; $s_{i-1}v_i(1)$ $v_i(j)v_i(j+1)$ $v_i(k_i)s_i$
, , ; $s_{i-1}\bar{v}_i(1)$ $\bar{v}_i(j)\bar{v}_i(j+1)$ $\bar{v}_i(k_i)s_i$
e , . $s_{n+i'-1}w_{i'}(j')$ $w_{i'}(j')s_{n+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). $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$

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

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

Então, qual é a relação entre o problema de e OP? Intuitivamente, o que vamos fazer é projetar uma matriz , 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 - . $G$ $h$ $s$ $t$

Os nossos matriz ter colunas, com índices a partir de . No seguinte constrcution um são dois valores satisfazem . As razões podem ser grandes potências de e . Seja $h$ $2n+1+\sum_i 2k_i+k$ $0$ $X$ $Y$ $1\ll X\ll Y$ $X/1, Y/X$ $k$ $n$ . $K_i=2i+2\sum_{j=1}^i k_i$

Para cada , , deixe (se a coordenada existir, o mesmo abaixo). $s_i$ $0\leq i\leq n$ $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$
Para cada , seja ; Para cada , deixá- . $x_i(j)$ $h(x_i(j),K_{i-1}+j)=X$ $\overline{x_i}(j)$ $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$
Para cada , e um literal na cláusula , seja . $\phi_{i'}$ $1\leq i'\leq k$ $x$ $\phi_{i'}$ $h(x,K_n+i')=1$
Todas as outras entradas são 0.

Por exemplo, para o gráfico de exemplo acima, a matriz correspondente é

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

Considere a programação atingindo o valor máximo. Como existem exatamente colunas em contendo , todas elas devem ser cobertas. Para a coluna que tem duas opções de , suponha que o planejamento a atribua a . Como a coluna deve ser atribuída a , pela consecutividade, temos que perder as colunas para $(2n+1)$ $h$ $Y$ $K_i+k_i+1$ $Y$ $s_i$ $K_i$ $s_i$ $K_i+1$ . O mesmo acontece se o planejamento atribuir a coluna a . $K_i+k_i$ $K_i+k_i+1$ $s_{i+1}$

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

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. $\textsf{NP-hard}$

Willard Zhan
fonte

Mas, na matriz de exemplo, se eu escolher

ainda assim posso alcançar o objetivo. O que estou fazendo de errado? Além disso, a

deve ser uma coluna para a direita e o

deve ser uma coluna para a esquerda

\bar{x_{1}}

$\overline{x_1}$

\bar{x_{2}}

$\overline{x_2}$

x_{3}

${x_3}$

X

$X$

\bar{x_{1}} (1)

$\overline{x_1}(1)$

X

$X$

\bar{x_{1}} (2)

$\overline{x_1}(2)$

rotia

@rotia Sim, e isso significa à esquerda você deve escolher

para ter

. Portanto, isso corresponde a uma tarefa satisfatória

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

4 X

$4X$

x_{1} = x_{2} = 1, x_{3} = 0

$x_1=x_2=1,x_3=0$

Willard Zhan

Você pode esclarecer o que "Suponha

um maior nos dois números de aparências dos literais

". 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? É

um literal ou um número?

k_{i}

$k_i$

x_{i}

$x_i$

\bar{x_{i}}

$\overline{x_i}$

k_{i}

$k_i$

@DW

é um número. Minha expressão não era de fato clara; Eu editei.

k_{i}

$k_i$

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

, de acordo com a fórmula, eu deveria ter apenas 450 pontos (assumindo que

é o número de cláusulas). Mas, escolhendo

i pode chegar a 452 pontos, escolhendo os quatro mais à direita

Y = 60

$Y = 60$

X = 7

$X = 7$

k

$k$

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

rotia

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 . Enviaremos unidades de fluxo de para . $s$ $t$ $k$ $s$ $t$
Crie vértices para representar os pontos de tempo entre os slots e uma aresta direcionada para cada com custo 0. $n+1$ $v_0, \dots, v_n$ $v_jv_{j+1}$ $0 \le j < n$
Para cada pessoa , crie o seguinte:
- Um vértice da sub-fonte e um vértice da sub-fonte . $s_i$ $t_i$
- Para cada , uma aresta de a custando (que consideramos 0 se ). $0 \le j < n$ $s_i$ $v_j$ $\Sigma_{k=1}^j{h(i,k)}$ $j=0$
- Para cada , uma aresta de a custando . $1 \le j \le n$ $v_j$ $t_i$ $-\Sigma_{k=1}^j{h(i,k)}$
- Uma aresta com custo 0. $ss_i$
- Uma aresta com custo 0. $t_it$

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 com um fluxo de 1 e uma aresta única chegada no com um fluxo de 1 , e todas as outras arestas incidentes em ou tenho 0 fluxo. Deixe estas flow-1 bordas para pessoa ser e : então $i$ $s_i$ $t_i$ $s_i$ $t_i$ $i$ $s_iv_j$ $v_kt_i$ $k \ge j$ , já que os únicos caminhos entre os vértices são aqueles que aumentam o índice. Se , a pessoa não recebe nenhum horário; caso contrário, a pessoa recebe o bloco de intervalos de tempo . $v$ $k = j$ $i$ $i$ $j+1, \dots, 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 como a diferença de duas somas de prefixo. As capacidades da unidade nas bordas entre os vtices atuam para impedir que 2 pessoas usem o mesmo intervalo de tempo. $s$ $j+1, \dots, k$ $v$

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

j_random_hacker
fonte

Isso pode falhar se alguma pessoa

leva uma rota de sua fonte de pia de outra pessoa e vice-versa?

i

$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

exceto

e todas as arestas

exceto

, e adicionando uma aresta

com enorme custo negativo

para cada

i

$i$

s s_{i}

$ss_i$

s s_{1}

$ss_1$

t_{i} t

$t_it$

t_{k} t

$t_kt$

t_{i} s_{i + 1}

$t_is_{i+1}$

- M

$-M$

1 \leq i < k

$1 \le i < k$ . O

s forçará a única unidade de fluxo a visitar todos os

dessas bordas da "tubulação" em qualquer solução ideal.

- M

$-M$

k - 1

$k-1$

Jrandom_hacker

@j_random_hacker, você está forçando uma ordem do

pessoas.

k

$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

, onde

é o primeiro bloco atribuído a pessoa

.) 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^{'} > i

$i' > i$

j^{'} < j

$j' < j$

j

$j$

i

$i$

j_random_hacker

@j_random_hacker O custo de

exigiria que

para ser o

th pessoa na solução óptima.

s_{i} v_{j}

$s_iv_j$

s_{i}

$s_i$

i

$i$

Chao Xu