article

An O(n) algorithm for the multiple-choice knapsack linear program

Author:

M. E. DyerAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 29, Issue 1

Pages 57 - 63

https://doi.org/10.1007/BF02591729

Published: 01 May 1984 Publication History

Abstract

An algorithm for solving the linear program associated with the multiple choice knapsack problem is described. The algorithm is shown to work in time linear in the number of variables. This improves the previously known best bound for this problem, and is optimal to within a constant factor.

References

[1]

A.V. Aho, J.E. Hopcroft and J.D. Ullman, The design and analysis of Computer algorithms (Addison-Wesley, Reading, MA, 1974).

Crossref

Google Scholar

[2]

E. Balas and E. Zemel, An algorithm for large zero-one knapsack problems, Operations Research 28 (1980) 1132-1154.

Google Scholar

[3]

M.E. Dyer, A geometrical approach to two-constraint linear programs with generalised upper bounds, Research Report, Teesside Polytechnic (1981).

Google Scholar

[4]

M.E. Dyer, Two-variable linear programs are solvable in linear time, Research Report, Teesside Polytechnic (1981).

Google Scholar

[5]

F. Glover and D. Klingman, A O(n log n) algorihtm for LP knapsacks with GUB constraints, Mathematical Programming 17 (1979) 345-361.

Google Scholar

[6]

T. Ibaraki, T. Hasegawa, K. Teranaka and J. Iwase, The multiple choice knapsack problem, Journal of the Operations Research Society of Japan 21 (1978) 59-95.

Crossref

Google Scholar

[7]

R.T. Rockafellar, Convex analysis (Princeton University Press, Princeton, NJ, 1970).

Google Scholar

[8]

P. Sinha and A. Zoltners, The multiple choice knapsack problem, Operations Research 27 (1979) 503-515.

Digital Library

Google Scholar

[9]

E. Zemel, The linear multiple choice knapsack problem, Operations Reseach 28 (1980) 1412-1423.

Digital Library

Google Scholar

[10]

M.E. Dyer, Linear time algorithms for two and three variable linear programs, SIAM Journal on Computing, to appear.

Google Scholar

[11]

N. Megiddo, Linear-time algorithms for linear-programming in R³ and related problems, Proceedings of 23rd IEEE Symposium on Foundations of Computer Science (1982), 329-338.

Digital Library

Google Scholar

[12]

N. Megiddo, Solving linear programming in linear time when the dimension is fixed, April 1982, submitted for publication.

Google Scholar

Cited By

View all

Montalbano Pde Givry SKatsirelos G(2022)Multiple-choice Knapsack Constraint in Graphical ModelsIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-08011-1_19(282-299)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-08011-1_19
Rahman TRouhani SGogate VRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Novel upper bounds for the constrained most probable explanation taskProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540997(9613-9624)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540997
Zhao KHua JYan LZhang QXu HYang CTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)A Unified Framework for Marketing Budget AllocationProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330700(1820-1830)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330700
Show More Cited By

An O(n) algorithm for the multiple-choice knapsack linear program

Recommendations

The linear multiple choice knapsack problem

The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. We present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The ...
A multi-criteria approach to approximate solution of multiple-choice knapsack problem

We propose a method for finding approximate solutions to multiple-choice knapsack problems. To this aim we transform the multiple-choice knapsack problem into a bi-objective optimization problem whose solution set contains solutions of the original ...
Transformation of a multi-choice linear programming problem

The aim of this paper is to transform a multi-choice linear programming problem to a standard mathematical programming problem where the right hand side goals of some constraints are 'multi-choice' in nature. For each of the constraint there may exist ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 29, Issue 1

May 1984

124 pages

ISSN:0025-5610

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 1984

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Montalbano Pde Givry SKatsirelos G(2022)Multiple-choice Knapsack Constraint in Graphical ModelsIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-08011-1_19(282-299)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-08011-1_19
Rahman TRouhani SGogate VRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Novel upper bounds for the constrained most probable explanation taskProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540997(9613-9624)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540997
Zhao KHua JYan LZhang QXu HYang CTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)A Unified Framework for Marketing Budget AllocationProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330700(1820-1830)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330700
Furini FMonaci MTraversi E(2018)Exact approaches for the knapsack problem with setupsComputers and Operations Research10.1016/j.cor.2017.09.01990:C(208-220)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.cor.2017.09.019
Bednarczuk EMiroforidis JPyzel P(2018)A multi-criteria approach to approximate solution of multiple-choice knapsack problemComputational Optimization and Applications10.1007/s10589-018-9988-z70:3(889-910)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10589-018-9988-z
Hamza AHefeeda M(2012)Energy-efficient multicasting of multiview 3D videos to mobile devicesACM Transactions on Multimedia Computing, Communications, and Applications10.1145/2348816.23488248:3s(1-25)Online publication date: 16-Oct-2012
https://dl.acm.org/doi/10.1145/2348816.2348824
Hamza AHefeeda MHefeeda MHsu C(2012)Multicasting of multiview 3D videos over wireless networksProceedings of the 4th Workshop on Mobile Video10.1145/2151677.2151687(43-48)Online publication date: 24-Feb-2012
https://dl.acm.org/doi/10.1145/2151677.2151687
Kanza YSafra ESagiv YDoytsher YAref WMokbel MSchneider M(2008)Heuristic algorithms for route-search queries over geographical dataProceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems10.1145/1463434.1463449(1-10)Online publication date: 5-Nov-2008
https://dl.acm.org/doi/10.1145/1463434.1463449
Zhou Y(2006)Improved multi-unit auction clearing algorithms with interval (multiple-choice) knapsack problemsProceedings of the 17th international conference on Algorithms and Computation10.1007/11940128_50(494-506)Online publication date: 18-Dec-2006
https://dl.acm.org/doi/10.1007/11940128_50
Mohr A(2002)Bit Allocation in Sub-linear Time and the Multiple-Choice Knapsack ProblemProceedings of the Data Compression Conference10.5555/882455.875022Online publication date: 2-Apr-2002
https://dl.acm.org/doi/10.5555/882455.875022
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

The linear multiple choice knapsack problem

A multi-criteria approach to approximate solution of multiple-choice knapsack problem

Transformation of a multi-choice linear programming problem

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations