A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Deterministic Approximation Algorithm for Maximum 2-Path Packing Um algoritmo de aproximação determinística para empacotamento máximo de 2 caminhos

Ruka TANAHASHI, Zhi-Zhong CHEN

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Este artigo trata do problema de empacotamento de 2 caminhos de peso máximo (M2PP), que é o problema de calcular um conjunto de caminhos disjuntos de vértices de comprimento 2 em um determinado grafo completo ponderado por arestas, de modo que o peso total das arestas no caminhos é maximizado. Anteriormente, Hassin e Rubinstein forneceram um algoritmo aleatório de aproximação de tempo cúbico para M2PP que atinge uma proporção esperada de - ε ≈ 0.5223 - ε para qualquer constante ε > 0. Refinamos seu algoritmo e desrandomizamos para obter um determinista algoritmo de aproximação de tempo cúbico para o problema que atinge um better razão (ou seja, 0.5265 - ε para qualquer constante ε>0).

Publicação
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.241-249
Data de publicação
2010/02/01
Publicitada
ISSN online
1745-1361
DOI
10.1587/transinf.E93.D.241
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science)
Categoria

autores

Palavra-chave