An improved randomized approximation algorithm for maximum triangle packing

DOI10.1016/J.DAM.2008.11.009MaRDI QIDQ1028142zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang

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 algorithmsmaximum triangle packingmaximum-weight \(b\)-matchingrandomized algorithms

Mathematics Subject Classification ID

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

Recommendations

• An Improved Randomized Approximation Algorithm for Maximum Triangle Packing
• Algorithms – ESA 2004
• An approximation algorithm for maximum triangle packing
• A randomized approximation algorithm for metric triangle packing
• A randomized approximation algorithm for metric triangle packing

Cites work

• An approximation algorithm for maximum triangle packing
• scientific article; zbMATH DE number 2011853 (Why is no real title available?)
• Maximum bounded 3-dimensional matching is MAX SNP-complete

Cited in

(20)

• Improved approximation algorithms for weighted 2-path partitions
• A local search algorithm for binary maximum 2-path partitioning
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• An approximation algorithm for maximum triangle packing
• Improved approximation algorithms for weighted 2-path partitions
• An Improved Randomized Approximation Algorithm for Maximum Triangle Packing
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
• Triangle packing in (sparse) tournaments: approximation and kernelization
• Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
• Algorithms – ESA 2004
• A randomized approximation algorithm for metric triangle packing
• A randomized approximation algorithm for metric triangle packing
• 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
• An improved approximation algorithm for metric triangle packing
• Approximating the maximum weight cycle/path partition in graphs with weights one and two
• Approximating the maximum weight cycle/path partition in graphs with weights one and two
• Approximation algorithms for cycle and path partitions in complete graphs
• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028142)