Gostaríamos de saber se existem resultados de aproximação conhecidos para a cardinalidade com restrição de - t- cut nos gráficos direcionados. Não conseguimos encontrar nenhum resultado na literatura.
O problema é definido da seguinte maneira:
Instância: Um gráfico direcionado , uma função de custo w : E → R + 0 , dois vértices s , t ∈ V e um número inteiro k .
Solução: Um - t- cut, ou seja, uma partição de V em dois conjuntos V 1 , V 2, de modo que s ∈ V 1 , t ∈ V 2 e o número de arestas que cruzam o corte são no máximo k , ie | { ( u , v ) ∈ E : u ∈ V 1 , v ∈ V 2 } | ≤ k .
Medida (para minimizar): O custo do corte:
Em " Problemas de cardinalidade restrita e multicritério (multi) corte ", os autores provam que esse problema é fortemente NP-Difícil, mesmo para gráficos não direcionados.
Estamos interessados principalmente em algoritmos de aproximação para gráficos direcionados, mas os resultados da aproximação para o caso não direcionado também podem ser úteis.
Obrigado por qualquer insight.
Respostas:
Podemos obter uma aproximação dois critérios da seguinte maneira (ou mais geralmente ( 1 + ε , 1 + 1 / ε ) aproximação de dois critérios).(2,2) (1+ε,1+1/ε)
Podemos assumir que sabemos o custo da solução ideal. Denotar que por . Seja w ′ ( u , v ) = w ( u , v )OPT
Considere a solução ideal(V1,V2). Então
∑(u,v)∈E( V 1 , V 2 )w′(u,v)=∑(u,v)∈E( V 1 , V 2 )(w(u,v)
fonte