검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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 최대 2경로 패킹을 위한 결정론적 근사 알고리즘

Ruka TANAHASHI, Zhi-Zhong CHEN

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문은 최대 가중치 2경로 패킹 문제(M2PP)를 다룬다. 이는 주어진 간선 가중치 완전 그래프에서 길이가 2인 정점 분리 경로 집합을 계산하여 각 간선의 총 가중치를 계산하는 문제이다. 경로가 최대화됩니다. 이전에 Hassin과 Rubinstein은 다음의 예상 비율을 달성하는 M2PP에 대한 무작위 입방 시간 근사 알고리즘을 제공했습니다. - ε ≒ 0.5223 - 임의의 상수 ε > 0에 대한 ε. 알고리즘을 개선하고 무작위화하여 다음을 얻습니다. 결정 론적 인 다음을 달성하는 문제에 대한 3차 시간 근사 알고리즘 비율(즉, 0.5265 - 임의의 상수 ε>0에 대해 ε).

발행
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.241-249
발행일
2010/02/01
공개일
온라인 ISSN
1745-1361
DOI
10.1587/transinf.E93.D.241
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science)
범주

작성자

키워드