An approximation algorithm for maximum triangle packing |
| |
| Authors: | Refael Hassin Shlomi Rubinstein |
| |
| Institution: | Department of Statistics and Operations Research, Tel Aviv University, 69978 Tel Aviv, Israel |
| |
| Abstract: | We present a randomized  -approximation algorithm for the weighted maximum triangle packing problem, for any given ε>0. This is the first algorithm for this problem whose performance guarantee is better than  . The algorithm also improves the best-known approximation bound for the maximum 2-edge path packing problem. |
| |
| Keywords: | Analysis of algorithms Maximum triangle packing 2-edge paths |
| 本文献已被 ScienceDirect 等数据库收录！ |
