Problema de localização das instalações capacitadas euclidianas

9

No Facility Capacitado Problema de Localização (CFLP) , nos é dado um conjunto de clientes e um conjunto de potenciais instalações . Cada cliente tem uma demanda que deve ser atendida por um ou mais recursos abertos. Cada instalação tem um custo de abertura e uma capacidade , que é a demanda máxima que a instalação posso atender. O custo de atender uma demanda unitária do cliente na instalação éCFjCdjiFfiuiijicij. Queremos abrir um subconjunto de instalações e atribuir demanda de clientes para instalações abertas, de modo que as demandas de todos os clientes sejam atendidas, nenhuma restrição de capacidade seja violada e o custo total da abertura de instalações e serviços seja minimizado. Os custos de serviço são não-negativos, simétricos e atendem à desigualdade do triângulo.

Arora em [ 1 , página 21] afirma que "Arora, Raghavan e Rao [ 2 ] fornecem um PTAS para o caso geométrico. Eles estendem o algoritmo ao caso capacitado, mas a solução final pode violar as restrições de capacidade em pequena quantidade". O que ele quer dizer com "pequena quantidade"? Eu acho que isso significa que eles fornecem um PTAS que viola as restrições de capacidade dentro do fator para um arbitrário . Isto está certo?(1+ϵ)ϵ>0

Quando examinei [ 2 ], o único resultado relacionado encontrado foi um algoritmo de tempo para encontrar uma solução aproximada para o capacitada problema -median quando temos capacidades uniformes. Arora se refere ao resultado acima em [ 1 ]?nO(log2(n/ϵ))(1+ϵ)k

[ 1 ] S. Arora. Esquemas de aproximação para problemas de otimização geométrica NP-hard: Uma pesquisa. Em matemática. Programação, Ser. B, vol. 97, pp. 43-69, 2003.

[ 2 ] S. Arora, P. Raghavan e S. Rao. Esquemas de aproximação para as medianas k euclidianas e problemas relacionados. Em Proc. 30º Simpósio da ACM sobre Teoria da Computação, pp 106-113, 1998.

Babak Behsaz
fonte

Respostas:

3

Se eu me lembrar corretamente, é necessário aproximar o número de clientes conectados a cada porta. Caso contrário, você obteria imediatamente algo como , onde é o número de portas em um subproblema. Ao aproximar esse número até um fator de toda a programação dinâmica, é possível obter um erro no final. Isso produziria tempos de execução semelhantes ao que você declarou acima.O(nO(g))g(1+ε/logn)(1+ε)

Sariel Har-Peled
fonte
Se eu entendi direito, você quer dizer que o algoritmo deles se estende a um QPTAS com violação de capacidades para o problema uniforme de localização de instalações capacitadas. Gostaria de saber se existe um PTAS com violação para esse problema. (1+ϵ)(1+ϵ)
Babak Behsaz
Isso é realmente uma pergunta interessante. Na época, parecia que se podia estender o artigo de Kolliopoulos e Rao para fazer isso.
precisa
Eu estava pensando o mesmo por um tempo, mas quando reli a prova do Teorema 4 de [Kolliopoulos-Rao-ESA'99] há alguns meses, descobri que você não pode aplicar esse teorema como uma caixa preta. O motivo é que, na prova, eles assumem que é possível atribuir um cliente a qualquer instalação aberta, enquanto no caso capacitado você pode violar as capacidades com esta modificação. Pode haver uma maneira simples de contornar isso, não pensei muito nisso.
perfil completo de Babak Behsaz