|
|||||
|
|
An improved randomized approximation algorithm for maximum triangle packing |
|
| Authors: | Zhi-Zhong Chen Ruka Tanahashi |
| Affiliation: | a Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan b Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong |
| Abstract: | This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of  for any constant ?>0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1−?) for any constant ?>0. |
| Keywords: | Maximum triangle packing Approximation algorithms Randomized algorithms Maximum-weight b-matching |
| 本文献已被 ScienceDirect 等数据库收录！ | |