[pt] Consideramos dois problemas de otimização combinatória: o
problema de transporte em redes de dutos (PTD) e o
problema
de busca com custos de acesso variados (PBC). No PTD, é
dado um grafo orientado G = (N,A) onde cada arco tem um
duto associado. Também é dado um conjunto de bateladas,
onde cada batelada está inicialmente em um nó ou arco do
grafo e tem um nó de destino. Algumas bateladas são
chamadas de proteláveis. O objetivo do PTD é encontrar
uma
sequência de operações que transporte todas as bateladas
não-proteláveis aos seus respectivos nós de destino.
Primeiro, demonstramos o PTD é NP-difícil, mesmo que o
grafo G seja acíclico. Em seguida, apresentamos um
algoritmo polinomial chamado de BPA. Este algoritmo
resolve
o PTDS, uma variação do PTD, para qualquer grafo G. Para
grafos acíclicos, o BPA minimiza uma função de custo
genérica. Para minimizar o makespan no PTDS, demonstramos
que não existe algoritmo polinomial n1-e - aproximado
para
nenhum E>0, a menos que P = NP, onde n é o tamanho da
instância. Este resultado também vale se G é acíclico e
planar. No PBC, são dados um vetor ordenado e o custo de
acessar cada um de seus n elementos. O objetivo do
problema
é encontrar uma estratégia de busca que minimize o custo
médio com probabilidades uniformes (PBCM) ou o custo do
pior caso (PBCN). Em ambos os casos, o melhor algoritmo
exato conhecido executa em tempo O(n3) e espaço O(n2).
Para
o PBCN, apresentamos o algoritmo da razão, que executa em
tempo O(n2) e espaço O(n). Este algoritmo sempre obtém
uma
solução de custo menor ou igual a 41n(n+1)/n, assumindo
que
a soma dos custos é 1. Além disso, desenvolvemos dois
algoritmos aproximados: um para o PBCM e outro para o
PBPC.
Ambos constroem soluções (2+E+0(1)) - aproximadas, para
qualquer E>0, em tempo e espaço O(n). / [en] We consider two combinatorial optimization problems the
pipeline transportation problem (PTD) and the problem of
searching with different access costs (PBC). In PTD, we are
given a directed graph G = (N,A) where each arc corresponds
to a pipeline. We are also given a set of batches, each
batch being initially located at an arc or node and having
a destination node. A subset of these batches are
considered as further batches. Our aim is to find a
sequence of pipeline operations leading all non-further
batches to their corresponding destination nodes. First, we
show that PDT is NP-hard, even for the case where G is
acyclic. Next, we present a polynomial algorithm called
BPA. This algorithm solves PTDS, a variation of PTD, for
general graphs. For acyclic graphs, BPA also minimizes a
general cost function. For the case of makespan
minimization for PTDS, we prove that there is no n1-e -
approximate algorithm for any E]0, unless P = NP, where n
is the instance size. The previous result also holds if G
is both ayclic and planar. In PBC, we are given an ordered
vector with n elements and the corresponding access costs.
Our aim is to find a search strategy that minimizes either
the average cost (PBPC). In both cases, the best known
exact algorithm requires in O(n3) time and O(n2) space. For
PBCM, we present the ratio algorithm, that requires O(n2)
time and O(n3)space. This algorithm always obtains a search
strategy with average cost at most 41n(n+1)/n, assuming the
sum of all access costs to be 1. Furthermore, we introduce
approximation algorithms for both PBCM and PBPC. Both of
them give (2+E+0(1)) - approximate solutions, for any E}0,
in O(n) time and space.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4356 |
| Date | 07 January 2004 |
| Creators | ARTUR ALVES PESSOA |
| Contributors | RUY LUIZ MILIDIU |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0024 seconds