Reference : Multi-Dimensional Vector Assignment Problems |

Scientific journals : Article | |||

Business & economic sciences : Quantitative methods in economics & management Physical, chemical, mathematical & earth Sciences : Mathematics | |||

http://hdl.handle.net/2268/171699 | |||

Multi-Dimensional Vector Assignment Problems | |

English | |

Dokka, Trivikram [] | |

Crama, Yves [Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >] | |

Spieksma, Frits C.R. [] | |

2014 | |

Discrete Optimization | |

Elsevier | |

14 | |

111-125 | |

Yes | |

International | |

1572-5286 | |

1873-636X | |

[en] Multi-dimensional assignment ; approximability ; worst-case analysis ; submodularity ; wafer-to-wafer | |

[en] We consider a special class of axial multi-dimensional assignment problems called multi-
dimensional 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 semi-conductor 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 case m = 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. | |

QuantOM - HEC Ecole de gestion | |

Politique Scientifique Fédérale (Belgique) = Belgian Federal Science Policy | |

PAI COMEX | |

Researchers | |

http://hdl.handle.net/2268/171699 | |

10.1016/j.disopt.2014.08.005 | |

A preliminary version of this paper, entitled "Approximation Algorithms for Multi-Dimensional Vector Assignment Problems", is available as a working paper at http://hdl.handle.net/2268/147977. This working paper contains a number of additional results which are only briefly mentioned in the article published in Discrete Optimization. |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.