zbMATH — the first resource for mathematics

Note: On the set-union Knapsack problem. (English) Zbl 0831.90088
The authors have defined a generalization of the 0-1 knapsack problem called the set-union knapsack problem (SKP): \[ \max\Biggl\{ \sum_{i\in K} v_i \Biggl|\sum_{j\in P_K} s_j\leq b,\;K\subseteq\{1,\dots, m\}\Biggr\}, \] where \(P_i\subseteq \{1,\dots, n\}\) so that \(\bigcup^\infty_{i= 1} P_i= \{1,\dots, n\}\) and \(P_K= \bigcup_{i\in K} P_i\). They show that the SKP remains NP- hard even in very restricted cases and present an exact dynamic programming algorithm that runs in polynomial time only for special cases. Two applications of SKP are also presented: machine loading in flexible manufacturing systems and the allocations of storage to fields in a data base.

90C10 Integer programming
90C35 Programming involving graphs or networks
90C39 Dynamic programming
Full Text: DOI
[1] Chinn, Journal of Graph Theory 6 pp 223– (1982)
[2] Chung, Discrete Mathematics 75 pp 113– (1989)
[3] and , ”Facets of the Dense Subhypergraph Problem,” European Journal of Operations Research (in press).
[4] and , ”A Column Generations Approach to Job Grouping for Flexible Manufacturing Systems,” Research Memorandum No. 92.010, Department of Quantitative Economics, University of Limburg, The Netherlands. 1992.
[5] and , Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
[6] , and , ”Component Assembly in the Semiconductor Industry: A Study of Covering in Graphs and Hypergraphs.” Working Paper No. 92/93-3-3, Graduate School of Business, University of Texas, 1992.
[7] , and , ”On a Generalization of the Knapsack Problem with Applications to Flexible Manufacturing Systems and Database Partitioning,” Working Paper No. 92/93-3-7, Graduate School of Business, University of Texas at Austin, 1992.
[8] Hirabayashi, Journal of the Operations Research Society of Japan 27 pp 205– (1984)
[9] ”A Constraint-Directed Method to Solve the Part Selection Problem in Flexible Manufacturing Systems Planning Stage,” in and (Eds.), Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, Elsevier Science Publishers BV, New York, 1986, pp. 297–309.
[10] Makedon, Discrete Applied Mathematics 23 pp 243– (1989)
[11] and , Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons, New York, 1990.
[12] Navathe, ACM Transactions on Database Systems 9 pp 680– (1984)
[13] ”Formulation and Heuristic Solutions for Parts Grouping and Tool Loading in Flexible Manufacturing Systems,” in and (Eds.), Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, Elsevier Science Publishers BV, New York, 1986, pp. 311–320.
[14] Rhys, Management Science 17 pp 200– (1970)
[15] Tang, Operations Research 36 pp 778– (1988)
[16] Whitney, Annals of Operations Research 3 pp 301– (1985)
[17] Yannakakis, Journal of the ACM 32 pp 950– (1985)
[18] , and , ”Product Sequencing in Multiple Product Setups for Electronic Card Assembly Process,” IBM Report No. TR51.0711, 1992.S
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.