Improved Approximation Algorithms for the Multiple Two-Stage Knapsack Problem
摘要
This paper studies approximation algorithms on the Multiple Two-stage Knapsack problem, which has received attention recently due to its applications in cloud computing. Given a set of two-stage jobs, the aim is to select a subset of jobs that can be completed by multiple parallel two-stage flowshops (knapsacks) within a time limit, in order to maximize the profit of the selected jobs. The problem is strongly NP-hard even when the number m of flowshops is 2. We focus on the problem where m is part of the input. A natural greedy approximation algorithm is proposed, which iteratively selects a subset of jobs with approximate maximum profit for flowshop from the current unselected jobs. The algorithm is shown to achieve an approximation ratio of \(1.582 + \epsilon \) for any constant \(\epsilon > 0\) , which improves the previously best-known algorithm with an approximation ratio of \(3 + \epsilon \) . In addition, we provide a faster algorithm with a tight approximation ratio of 4.