|
|||||
|
|
An improved randomized approximation algorithm for maximum triangle packing |
|
| Authors: | Zhi-Zhong Chen Ruka Tanahashi |
| Institution: | 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 _method=retrieve& _eid=1-s2 0-S0166218X08005313& _mathId=si5 gif& _pii=S0166218X08005313& _issn=0166218X& _acct=C000051805& _version=1& _userid=1154080& md5=440dd01f49aaeac6b40c437ff73838b2')" style="cursor:pointer b-matching" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">b-matching |
| 本文献已被 ScienceDirect 等数据库收录！ | |