[pt] DOIS PROBLEMAS DE OTIMIZAÇÃO EM GRAFOS: TRANSPORTE EM REDES DE DUTOS E BUSCA COM CUSTOS DE ACESSOS

ARTUR ALVES PESSOA

[en] TWO GRAPH OPTIMIZATION PROBLEMS: PIPELINE TRANSPORTATION AND SEARCHING WITH ACCESS COSTS

dc.contributor	RUY LUIZ MILIDIU
dc.creator	ARTUR ALVES PESSOA
dc.date	2004-01-07
dc.date.accessioned	2022-09-21T21:42:12Z
dc.date.available	2022-09-21T21:42:12Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4356@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4356@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.4356
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42456
dc.description	[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).
dc.description	[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.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] OTIMIZACAO
dc.subject	[pt] ALGORITMOS APROXIMADOS
dc.subject	[pt] ARVORES DE BUSCA
dc.subject	[pt] GRAFOS
dc.subject	[pt] COMPLEXIDADE
dc.subject	[pt] DUTO
dc.subject	[en] TRANSPORTATION
dc.subject	[en] APPROXIMATION ALGORITHMS
dc.subject	[en] SEARCH TREES
dc.subject	[en] GRAPHS
dc.subject	[en] COMPLEXITY
dc.subject	[en] PIPE
dc.subject	[en] OPTIMIZATION
dc.title	[pt] DOIS PROBLEMAS DE OTIMIZAÇÃO EM GRAFOS: TRANSPORTE EM REDES DE DUTOS E BUSCA COM CUSTOS DE ACESSOS
dc.title	[en] TWO GRAPH OPTIMIZATION PROBLEMS: PIPELINE TRANSPORTATION AND SEARCHING WITH ACCESS COSTS
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record