Solving the set packing problem via a maximum weighted independent set heuristic (Q826368): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:36, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving the set packing problem via a maximum weighted independent set heuristic |
scientific article |
Statements
Solving the set packing problem via a maximum weighted independent set heuristic (English)
0 references
4 January 2021
0 references
Summary: The set packing problem (SPP) is a significant NP-hard combinatorial optimization problem with extensive applications. In this paper, we encode the set packing problem as the maximum weighted independent set (MWIS) problem and solve the encoded problem with an efficient algorithm designed to the MWIS problem. We compare the independent set-based method with the state-of-the-art algorithms for the set packing problem on the 64 standard benchmark instances. The experimental results show that the independent set-based method is superior to the existing algorithms in terms of the quality of the solutions and running time obtained the solutions.
0 references