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

randomized algorithmsapproximation algorithmsmaximum triangle packingmaximum-weight \(b\)-matching

Mathematics Subject Classification ID

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

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

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

Cited in

(17)

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

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)