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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Approximation Algorithms for the Multiple Two-Stage Knapsack Problem

  • Kang Zhao,
  • Guangwei Wu,
  • Guozhen Rong,
  • Yunyun Sun,
  • Feng Shi

摘要

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.