Multiple subset sum with inclusive assignment set restrictions

DOI10.1002/nav.20466zbMath1267.90122OpenAlexW2075277223MaRDI QIDQ5300451

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

Publication date: 27 June 2013

Published in: Naval Research Logistics (NRL) (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)

Related Items (3)

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

Cites Work

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

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