Greedy Local Improvement and Weighted Set Packing Approximation

DOI10.1006/jagm.2000.1155zbMath0974.68238MaRDI 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 sets; weighted \(k\)-set packing problem

Mathematics Subject Classification ID

68W25: Approximation algorithms

05B40: Combinatorial aspects of packing and covering

Related Items

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