An improved randomized approximation algorithm for maximum triangle packing

DOI10.1016/J.DAM.2008.11.009zbMATH Open1172.68681OpenAlexW2032640598MaRDI QIDQ1028142FDOQ1028142

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

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

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)

Cites Work

• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An approximation algorithm for maximum triangle packing
• Title not available (Why is that?)

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
• An improved approximation algorithm for metric triangle packing
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum 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
• Approximation algorithms for the maximum-weight cycle/path packing problems
• A local search algorithm for binary maximum 2-path partitioning
• 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)