The Continuous Knapsack Problem with Capacities

doi:10.1007/s40305-020-00298-6

Journal of the Operations Research Society of China ›› 2021, Vol. 9 ›› Issue (3): 713-721.doi: 10.1007/s40305-020-00298-6

The Continuous Knapsack Problem with Capacities

Huynh Duc Quoc¹, Nguyen Chi Tam¹, Tran Hoai Ngoc Nhan²

1 Department of Mathematics, College of Natural Science, Can Tho University, Can Tho City 900900, Vietnam;
2 Faculty of Basic Sciences, Vinh Long University of Technology Education, Vinh Long 940000, Vietnam

Received:2019-08-10 Revised:2020-03-04 Online:2021-09-30 Published:2021-09-26
Contact: Nguyen Chi Tam,nctamctu@gmail.com;Huynh Duc Quoc,hdquoc@ctu.edu.vn;Tran Hoai Ngoc Nhan,tranhoaingocnhan@gmail.com E-mail:nctamctu@gmail.com;hdquoc@ctu.edu.vn;tranhoaingocnhan@gmail.com

Abstract

Abstract: We address a variant of the continuous knapsack problem, where capacities regarding costs of items are given into account. We prove that the problem is NP-complete although the classical continuous knapsack problem is solvable in linear time. For the case that there exists exactly one capacity for all items, we solve the corresponding problem in O(n log n) time, where n is the number of items.

Key words: Knapsack problem, Complexity, Capacity, Polynomially solvable

CLC Number:

Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan. The Continuous Knapsack Problem with Capacities[J]. Journal of the Operations Research Society of China, 2021, 9(3): 713-721.

TrendMD

[1]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[2]	Yan Li, Sheng-Long Hu, Jie Wang, Zheng-Hai Huang. An Introduction to the Computational Complexity of Matrix Multiplication [J]. Journal of the Operations Research Society of China, 2020, 8(1): 29-43.
[3]	Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard. A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(1): 145-164.
[4]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.
[5]	Qi Qi, Wen-Wei Wang, Ling-Fei Yu. Competitive and Collaborative Influence in Social Networks [J]. Journal of the Operations Research Society of China, 2019, 7(1): 169-182.
[6]	Mohammad Pirhaji,Hossein Mansouri,Maryam Zangiabadi. A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2018, 6(4): 529-544.
[7]	Jian-Chao Huang, Jin-Yan Fan. Global Complexity Bound of the Inexact Levenberg–Marquardt Method [J]. Journal of the Operations Research Society of China, 2018, 6(3): 417-428.
[8]	Yu-Hong Dai, Rui Diao, Kai Fu. Complexity Analysis and Algorithm Design of Pooling Problem [J]. Journal of the Operations Research Society of China, 2018, 6(2): 249-266.
[9]	Behrouz Kheirfam. A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(2): 301-315.
[10]	Roghayeh Etemad · Behrooz Alizadeh. Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs [J]. Journal of the Operations Research Society of China, 2017, 5(3): 347-361.
[11]	Xiang Gao· Shu-Zhong Zhang. First-Order Algorithms for Convex Optimization with Nonseparable Objective and Coupled Constraints [J]. Journal of the Operations Research Society of China, 2017, 5(2): 131-.
[12]	Yi-Yong Li· Qing-Zhi Yang · Xi He. A Method with Parameter for Solving the Spectral Radius of Nonnegative Tensor [J]. Journal of the Operations Research Society of China, 2017, 5(1): 3-.
[13]	Chang-He Liu,Dan Wu,You-Lin Shang. A New Infeasible-Interior-Point Algorithm Based on Wide Neighborhoods for Symmetric Cone Programming [J]. Journal of the Operations Research Society of China, 2016, 4(2): 147-.
[14]	Xiang-Feng Wang. On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities [J]. Journal of the Operations Research Society of China, 2015, 3(3): 347-.
[15]	Soodabeh Asadi · Hossein Mansouri ·Maryam Zangiabadi. A Class of Path-Following Interior-Point Methods for P∗(κ)-Horizontal Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2015, 3(1): 17-.

The Continuous Knapsack Problem with Capacities

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments