Greedy Local Improvement and Weighted Set Packing Approximation

DOI10.1006/jagm.2000.1155zbMath0974.68238OpenAlexW2043260929MaRDI QIDQ2729651

Magnús M. Halldórsson, Barun Chandra

Publication date: 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2000.1155

zbMATH Keywords

weighted setsweighted \(k\)-set packing problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Related Items

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ A dynamic programming algorithm for tree-like weighted set packing problem ⋮ The limits of local search for weighted \(k\)-set packing ⋮ The quality of equilibria for set packing and throughput scheduling games ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ Matchings with lower quotas: algorithms and complexity ⋮ Local search algorithms for the maximum carpool matching problem ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ Parameterized algorithms for weighted matching and packing problems ⋮ Combinatorial auctions ⋮ An approximation algorithm for maximum triangle packing ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Robust Independence Systems ⋮ Unnamed Item ⋮ Distributed algorithms for matching in hypergraphs