On a posterior evaluation of a simple greedy method for set packing

DOI10.1007/S11590-008-0085-6MaRDI QIDQ941055zbMATH OpenOpenAlexFDO

Authors Roy H. Kwon, Georgios V. Dalakouras, Cheng Wang

Publication date 4 September 2008

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-008-0085-6

zbMATH Keywords

greedy heuristicsinteger programminglinear programming dualityprimal-dual approximationweighted set packing

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Mathematical Foundations of Computer Science 2005
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Data dependent worst case bounds for weighted set packing
• Average case analysis of the set packing problem
• scientific article; zbMATH DE number 1305405

Cites work

• ``A posteriori evaluation of bin packing approximation algorithms
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Approximation algorithms for NP-hard problems.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Data dependent worst case bounds for weighted set packing
• Experimental analysis of approximation algorithms for the vertex cover and set covering problems
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Set Partitioning: A survey
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(1)

• Solving the set packing problem via a maximum weighted independent set heuristic

This page was built for publication: On a posterior evaluation of a simple greedy method for set packing

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