• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Multi-dimensional vector assignment problems
【24h】

Multi-dimensional vector assignment problems

机译：多维向量分配问题

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

摘要

We consider a special class of axial multi-dimensional assignment problems called multidimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semiconductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the casem = 3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension p.
机译：我们考虑一类特殊的轴向多维分配问题，称为多维矢量分配（MVA）问题。 MVA问题的一个实例由m个不相交集定义，每个不相交集包含n个具有非负整数分量的p维向量，以及在向量上定义的成本函数。向量的m元组的代价定义为它们的分量最大值的代价。现在的问题是将m个向量集合划分为n个m-元组，以使来自同一集合的两个向量都不在同一个m-元组中，从而使m-元组的成本总和最小化。主要动机来自半导体制造中的成品率优化问题。我们考虑MVA的一类特定的多项式时间启发式算法，即顺序启发式算法，并研究它们的近似比率。特别地，我们表明，当成本函数为单调和次加性时，顺序启发式算法对于每个固定m均具有有限的近似比率。此外，当成本函数为亚模时，对于特定的顺序启发式方法，当成本函数为加性时，我们建立较小的近似比率。我们提供了一些例子来说明分析的严格性。此外，我们证明即使对于casem = 3和二进制输入向量，MVA问题也是APX难题。最后，我们证明了在固定维为p的二元向量的特殊情况下，可以在多项式时间内解决该问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号