The multiple knapsack problem with compatible bipartite graphs
The multiple knapsack problem with compatible bipartite graphs
- Author(s): Jianping Li ; Weidong Li ; Hao Wang
- DOI: 10.1049/cp.2015.0613
For access to this article, please select a purchase option:
Buy conference paper PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015) — Recommend this title to your library
Thank you
Your recommendation has been sent to your librarian.
- Author(s): Jianping Li ; Weidong Li ; Hao Wang Source: 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015), 2015 page ()
- Conference: 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015)
- DOI: 10.1049/cp.2015.0613
- ISBN: 978-1-78561-085-1
- Location: Luoyang, China
- Conference date: 21-24 Aug. 2015
- Format: PDF
The multiple knapsack problem is to pack some items into given knapsacks, such that the sum of the knapsack profits is maximized. This paper is concerned with a variant of the multiple knapsack problem, called the multiple knapsack problem with compatible bipartite graph (MKPCBG), where two items can be packed into the same knapsack only if their corresponding vertices are adjacent in the given compatible bipartite graph. Under two different objectives, we prove that the MKPCBG problem is strongly NP-hard, design some 1/2-approximation algorithms, and design two optimal algorithms for the special case where all knapsacks have the same capacity.
Inspec keywords: knapsack problems; approximation theory; graph theory; computational complexity
Subjects: Combinatorial mathematics; Applications of systems theory; Computational complexity; Interpolation and function approximation (numerical analysis)
Related content
content/conferences/10.1049/cp.2015.0613
pub_keyword,iet_inspecKeyword,pub_concept
6
6