Algoritmos de aproximação para corte mínimo direcionado com restrições de cardinalidade

8

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.st

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 .G=(V,E)w:ER0+s,tVk

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 .stVV1,V2sV1tV2k|{(u,v)E:uV1,vV2}|k

Medida (para minimizar): O custo do corte:

(u,v)E:uV1,vV2w(u,v)

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.

Steven
fonte
Desculpe, não é uma resposta, na verdade, quero perguntar como transferir a aproximação de dois critérios para a aproximação de mono-critérios? por favor me perdoe.
Jianhao Ma

Respostas:

11

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)

w(u,v)=w(u,v)OPT+1k.
(V1,V2)
(u,v)E(V1,V2)w(u,v)=(u,v)E(V1,V2)(w(u,v)OPT+1k)=1+|E(V1,V2)|k2.

st(V1,V2)Gw2(V1,V2)

E(V1,V2)=(u,v)E(V1,V2)1k(u,v)E(V1,V2)w(u,v)2k
(u,v)E(V1,V2)w(u,v)OPT(u,v)E(V1,V2)w(u,v)2OPT.
Yury
fonte
Muito obrigado. Seu algoritmo é muito interessante e perspicaz. Infelizmente, parece que um algoritmo de aproximação bicritério não é suficiente para nós, pois precisamos que toda solução aproximada seja possível através da restrição de cardinalidade. Você sabe se algum resultado desse tipo é conhecido na literatura? Obrigado novamente!
Steven
k(k+1)/2V=s,t,xsx(k+1)/2xtk+1(k+1)/2xe=2/(k+1)sxxe=12/(k+1)xt1(k+1)/2.
Yury 27/03
(k+1)/2