![](/images/graphics-bg.png)
Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic
Joint Authors
Li, Ruizhi
Jiang, Jianhua
Wang, Yupan
Hu, Shuli
Ouyang, Dantong
Yin, Minghao
Source
Mathematical Problems in Engineering
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-12-16
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Li, Ruizhi& Wang, Yupan& Hu, Shuli& Jiang, Jianhua& Ouyang, Dantong& Yin, Minghao. 2020. Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic. Mathematical Problems in Engineering،Vol. 2020, no. 2020, pp.1-11.
https://search.emarefa.net/detail/BIM-1194153
Modern Language Association (MLA)
Li, Ruizhi…[et al.]. Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic. Mathematical Problems in Engineering No. 2020 (2020), pp.1-11.
https://search.emarefa.net/detail/BIM-1194153
American Medical Association (AMA)
Li, Ruizhi& Wang, Yupan& Hu, Shuli& Jiang, Jianhua& Ouyang, Dantong& Yin, Minghao. Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic. Mathematical Problems in Engineering. 2020. Vol. 2020, no. 2020, pp.1-11.
https://search.emarefa.net/detail/BIM-1194153
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1194153