Multiple subset sum with inclusive assignment set restrictions

DOI10.1002/NAV.20466zbMATH Open1267.90122OpenAlexW2075277223MaRDI QIDQ5300451FDOQ5300451

Chung-Lun Li, Joseph Y.-T. Leung, Hans Kellerer

Publication date: 27 June 2013

Published in: Naval Research Logistics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/nav.20466

zbMATH Keywords

subset sumworst case analysispolynomial time approximation schemeinclusive assignment sets

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• An approximation algorithm for the generalized assignment problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Bin packing can be solved within 1+epsilon in linear time
• A 3/4-approximation algorithm for multiple subset sum
• The multiple subset sum problem
• A PTAS for the multiple subset sum problem with different knapsack capacities
• Scheduling parallel machines with inclusive processing set restrictions
• Parallel machine scheduling with nested job assignment restrictions
• Fast approximation algorithms for job scheduling with processing set restrictions
• Tight approximation algorithms for maximum general assignment problems
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• LP based heuristics for the multiple knapsack problem with assignment restrictions
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem

Cited In (3)

• Coordinated scheduling of production and delivery with production window and delivery capacity constraints
• Online packing of arbitrary sized items into designated and multipurpose bins
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

This page was built for publication: Multiple subset sum with inclusive assignment set restrictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300451)