• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
【24h】

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

机译：多维分配问题的最小化平方误差总和的近似算法

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

摘要

Given a complete k-partite graph G = (V-1, V-2,..., V-k; E) satisfying vertical bar V-1 vertical bar = vertical bar V-2 vertical bar = ... = vertical bar V-k vertical bar = n and weights of all k-cliques of G, the k-dimensional assignment problem finds a partition of vertices of G into a set of(pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q(d) and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem. We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2 - 3/k) times the optimal value. Our result improves the previously known bound (4 - 6/k) of the approximation ratio.
机译：给定完整的k零件图G =（V-1，V-2，...，Vk; E）满足垂直线V-1垂直线=垂直线V-2垂直线= ... =垂直线Vk垂直条= n和G的所有k-clique的权重，k维分配问题找到G的顶点的划分为一组（成对不相交）n个k-cliques，这使选定的集团的权重总和最小化。在本文中，我们考虑一种情况，其中团的权重由团产生的边的给定权重之和定义。另外，我们假设G的顶点嵌入d维空间Q（d），并且边缘的权重由其两个端点之间的欧几里得距离的平方确定。我们描述这些问题实例来自数据关联问题的多维高斯模型。我们提出了该问题的二阶锥规划松弛和多项式时间随机舍入程序。我们表明，通过我们的算法获得的预期目标值的上限是最佳值的（5/2-3 / k）倍。我们的结果改善了近似比率的先前已知范围（4-6 / k）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号