...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Naval Research Logistics >Multiple Subset Sum with Inclusive Assignment Set Restrictions
【24h】

Multiple Subset Sum with Inclusive Assignment Set Restrictions

机译：具有包含分配集限制的多个子集总和

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492-approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 546-563, 2011
机译：在传统的多子集和问题（MSSP）中，存在一组给定的项目和给定的一组具有相同容量的垃圾箱（或背包）。目的是选择一个子集并将其包装到箱中，以使所选项目的总重量最大。但是，在MSSP的许多应用中，垃圾箱具有分配限制。在本文中，我们研究具有包含性分配集限制的子集总和问题，其中一个项目的分配集（即，该项目可能分配给的仓位集合）必须是分配的子集或超集套另一个项目。我们开发了一种高效的0.6492近似算法，并通过计算实验测试了其有效性。我们还针对此问题开发了多项式时间近似方案。 ©2011 Wiley Periodicals，Inc.海军研究物流58：546-563，2011

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号