An improved randomized approximation algorithm for maximum triangle packing

DOI10.1016/J.DAM.2008.11.009zbMath1172.68681OpenAlexW2032640598MaRDI QIDQ1028142

Lusheng Wang, Ruka Tanahashi, Zhi-Zhong Chen

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.11.009

zbMATH Keywords

approximation algorithmsrandomized algorithmsmaximum triangle packingmaximum-weight \(b\)-matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Randomized algorithms (68W20) Combinatorial aspects of packing and covering (05B40)

Related Items (10)

Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems ⋮ MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS ⋮ Approximation algorithms for the maximum-weight cycle/path packing problems ⋮ Improved approximation algorithms for cycle and path packings ⋮ A deterministic approximation algorithm for metric triangle packing ⋮ A randomized approximation algorithm for metric triangle packing ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ An improved approximation algorithm for metric triangle packing

Cites Work

• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An approximation algorithm for maximum triangle packing

This page was built for publication: An improved randomized approximation algorithm for maximum triangle packing