Name
Abstract | ||
|---|---|---|
SPTP is a model for the pipeline transportation of petroleum products. It uses a directed graph G, where arcs represent pipes and nodes represent locations. In this paper, we analyze the complexity of finding a minimum makespan solution to SPTP. This problem is called SPTMP. We prove that, for any fixed ¿0, there is no ¿1¿¿-approximate algorithm for the SPTMP unless P=NP, where ¿ is the input size. This result also holds if G is both planar and acyclic. If G is acyclic, then we give a m-approximate algorithm to SPTMP, where m is the number of arcs in G. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(03)00291-3 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
petroleum product,approximate algorithm,approximability,transportation,graph g,m-approximate algorithm,pipeline transportation,minimum makespan solution,complexity,makespan minimization,petroleum,oil pipeline,input size | Journal | 306 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.50 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruy Luiz Milidiú | 1 | 192 | 20.18 |
| Artur Alves Pessoa | 2 | 270 | 24.30 |
| Eduardo Sany Laber | 3 | 229 | 27.12 |