A linear time algorithm for the balanced {0,1}-knapsack problem

Vo Nguyen Minh Hieu * , Tran Thu Le and Nguyen Ngoc Dang Duy

* Corresponding author (hieub1609966@student.ctu.edu.vn)

Article Sidebar

Full Text: PDF

Received: 04 May 2019
Revised: 27 Jul 2019
Accepted: 30 Oct 2019
Published: 30 Oct 2019
Title: A linear time algorithm for the balanced {0,1}-knapsack problem
DOI: 10.22144/ctu.jvn.2019.132
Views
284
Downloads
144
Crossref
Scopus
Google Scholar
Europe PMC
How to Cite
Hiếu, V. N. M., Lễ, T. T., & Duy, N. N. Đ. (2019). A linear time algorithm for the balanced {0,1}-knapsack problem. CTU Journal of Science, 55(5), 82-87. https://doi.org/10.22144/ctu.jvn.2019.132
Issue
Vol. 55 No. 5 (2019)
Section
Natural Sciences

Abstract

In this paper, a variant of the balanced optimization problem, where the knapsack constraint is associated, is considered. To solve this problem, a special structure of the feasible solutions is explored. Based on this investigation, a dynamic approach is developed to solve the mentioned problem in linear time.
Keywords: Balance problem, dynamic programing, knapsack problem

Tóm tắt

Trong bài báo này, một biến thể của bài toán tối ưu cân bằng với ràng buộc có dạng xếp ba lô được nghiên cứu. Để giải quyết bài toán, một cấu trúc đặc biệt của tập các phương án chấp nhận được chỉ ra. Dựa vào đó, một thuật toán quy hoạch động được đề xuất để giải bài toán đã nêu trong thời gian đa thức.
Từ khóa: Bài toán xếp ba lô, Bài toán cân bằng, Quy hoạch động

Article Details

References

Arora, S., 1998. Polynomial time approximation schemes forEuclidean traveling salesman and other geometric problems. Journal of theACM (JACM). 45(5): 753-782.

Applegate, D.L., Bixby, R.M., Chvátal, V. and Cook, W.J., 2007. The Traveling Salesman Problem: A Computational Study. Princeton University Press. Princeton, NJ, USA. 606 pages.

Dantzig, G.B. and Ramser, J.H., 1959. The Truck Dispatching Problem. Management Science. 6(1): 80-91.

Danzig, G. B. and Thapa, M. N., 2003. Linear Programing 2: Theory and Extensions. Springer – Verlag. The United States of America. 448 pages.

Hoare, C.A.R., 1962. Quicksort. The computer journal. 5(1): 10 -16.

Kamarkar, N., Adler, I., Resende, M. and Geraldo, V., 1989. An Implementation Of Karmarkar’s Algorithm For Linear Programming. Mathematical Programming. 44(1): 297-335.

Kariv, O. and S.L. Hakimi, S.L., 1979a. An algorithmic approach to network locationproblems, I. The p-centers, SIAM Journal onApplied Mathematics. 37: 513-538.

Kariv, O. and Hakimi, S.L., 1979b. An algorithmic approach to network location problems, II. The p-medians. SIAM Journal on Applied Mathematics. 37: 536-560.

Kuhn, H. W., 1955. The Hungarian Method forthe Assignment Problem. Naval ResearchLogistics Quarterly. 2: 83-97.

Kuhn, H. W., 1956. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly. 3: 253-258.

Laporte, G. and Martello, S., 1990. The selective travelling salesman problem. Discrete Applied Mathematics. 26(2-3):193-207.

Martello, S., Pulleyblank, W.R., Toth, P. and De Werra, D., 1984. Balanced Optimization Problems. Operations Research Letters. 3: 275-278.

Martello, S. and Toth, P., 1990. Knapsack problems: algorithms and computer implementations. John Wiley &Sons, Inc. New York, NY, USA. 296 pages.

Martello, S., Pisinger, D. and Toth, P., 2000. New trends in exact algorithms for the0–1 knapsack problem. European Journal ofOperational Research. 123(2): 325-332.

Nguyen, K. and Vui, P., 2016. The inverse p-maxian problem on trees with variable edge lengths. Taiwanese Journal of Mathematics, 20(6): 1437-1449.

Nguyen, K.T., Nguyen-Thu, H. and Hung, N.T., 2018. On the complexity of inverse convex ordered1-median problem on the plane and on tree networks. Mathematical Methods of Operations Research, pp.1-13.

Nguyen, K.T., 2019. The inverse1-center problem on cycles with variable edge lengths. Central European Journal of Operations Research, 27(1): 263-274.

Nguyen, K.T., Hung, N.T., Nguyen-Thu, H., Le, T.T. and Pham, V.H., 2019. On some inverse1-center location problems. Optimization, 68(5): 999-1015.

Pisinger, D., Pferschy, U. and Kellerer, H., 2004. Knapsack Problems. Springer.

Wolsey, L.A., 1998. Integer Programming. John Wiley and Sons Inc, New York, United States.

Zhong, C., Malinen, M., Miao, D. and Fränti, P., 2015. A fast minimum spanning tree algorithm based onK-means. Information Sciences. 295: 1-17.

Zia, M., Cakir, Z. and Seker, D.Z., 2017. A New Spatial Approach for Efficient Transformation of Equality-Generalized TSP to TSP. Free and Open Source Software for Geospatial (FOSS4G) Conference Proceedings. 17(5): 14-22.