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

DOI10.1007/s11590-008-0085-6zbMath1177.90296OpenAlexW2120279149MaRDI QIDQ941055

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

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

integer programminggreedy heuristicslinear programming dualityprimal-dual approximationweighted set packing

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• ``A posteriori evaluation of bin packing approximation algorithms
• 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
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Worst-Case Analysis of Heuristic Algorithms
• Set Partitioning: A survey

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