检索结果-内蒙古大学图书馆

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

DISCRETE APPLIED MATHEMATICS 2009年第9期157卷 2124-2135页

作者： Kuroki, Yusuke Matsui, Tomomi Univ Tokyo Grad Sch Informat Sci & Technol Bunkyo Ku Tokyo 1138656 Japan Chuo Univ Dept Informat & Syst Engn Fac Sci & Engn Bunkyo Ku Tokyo 1128551 Japan

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. (C) 2007 Elsevier B.V. All rights reserved.

关键词： multidimensional assignment problem Approximation algorithm Second-order cone programming Data-association problem Data fusion

来源：评论

学校读者我要写书评

暂无评论

A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1997年第2期8卷 129-150页

作者： Poore, AB Robertson, AJ BDM FED INC BOULDERCO 80301

Large classes of data association problems in multiple target tracking applications involving both multiple and single sensor systems can be formulated as multidimensional assignment problems. These NP-hard problems are large scale and sparse with noisy objective function values, but must be solved in ''real-time''. Lagrangian relaxation methods have proven to be particularly effective in solving these problems to the noise level in real-rime, especially for dense scenarios and for multiple scans of data from multiple sensors. This work presents a new class of constructive Lagrangian relaxation algorithms that circumvent some of the deficiencies of previous methods. The results of several numerical studies demonstrate the efficiency and effectiveness of the new algorithm class.

关键词： Lagrangian relaxation multidimensional assignment problem combinatorial optimization nonsmooth optimization

来源：评论

学校读者我要写书评

暂无评论

Random assignment problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期194卷 1-17页

作者： Krokhmal, Pavlo A. Pardalos, Panos M. Univ Iowa Dept Mech & Ind Engn Iowa City IA 52242 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem's solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc. (c) 2007 Elsevier B.V. All rights reserved.

关键词： Random assignment problems Linear assignment problem Quadratic assignment problem multidimensional assignment problem Bottleneck assignment problem Probabilistic analysis Asymptotic analysis Fitness landscape analysis

来源：评论

学校读者我要写书评

暂无评论

Multi-criteria assignment policies to improve global effectiveness of medico-social service sector

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2017年 61卷 21-34页

作者： Osorio, Geovanny Monteiro, Thibaud Trilling, Lorraine Albert, Frederic INSA Lyon DISP Lab Decis & Informat Syst Prod Bat Jules Verne19 Av Jean Capelle F-69621 Villeurbanne France Fdn OVE 19 Rue Marius Grosso F-69120 Vaulx En Velin France Minist Sante 14 Ave Duquesne F-75007 Paris France

In this paper, we propose a multi-criteria approach in order to reduce the waiting time on the assignment of users to medico-social institutions. The main goal is to ascertain whether alternative assignment policies can improve global response to users' demands, and to assess the performances of each alternative (scenario) compared to the current practice. We propose a mathematical model of user assignment to medico-social structures and professionals, under constraints of resource capacity, professionals' skills and user requirements (formulated in an individual support project). With alternative assignment policies, users' needs could be covered partially. They also authorize the involvement of several structures and several professionals in the response to the request. A mixed integer linear programming solver is used to solve this assignment problem, following a lexicographic approach in case of partial coverage policy. For some assignment policies that have long calculation times, we propose a simulated annealing approach in order to speed up the resolution. In order to validate simulated annealing approach, we compared it with a greedy randomized adaptive search procedure. The problem is solved for instances where we have real size data for a set of institutions for disabled children and teenagers. We present and compare computational results over several scenarios, highlighting the improvement provided by each alternative assignment policy.

关键词： multidimensional assignment problem Resources allocation MILP Resources utilization Medico-social service sector Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

引用

OPTIMIZATION LETTERS 2010年第4期4卷 609-617页

作者： Kammerdiner, Alla Krokhmal, Pavlo A. Pardalos, Panos M. Univ Iowa Dept Mech & Ind Engn Iowa City IA 52242 USA AFRL RWGN NRC Eglin AFB FL 32547 USA Univ Florida Dept Ind & Syst Engn Ctr Appl Optimizat Gainesville FL 32611 USA

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.

关键词： Hypergraph matchings Combinatorial optimization multidimensional assignment problem Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Selected topics on assignment problems

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期123卷 257-302页

作者： Burkard, RE Graz Univ Technol Inst Math A-8010 Graz Austria

We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignment problems and applications, multidimensional assignment problems, quadratic assignment problems, in particular lower bounds, special cases and asymptotic results, biquadratic and communication assignment problems. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： assignment problem bottleneck assignment problem multidimensional assignment problem quadratic assignment problem special cases asymptotic theory quadratic bottleneck assignment problem biquadratic assignment problem communication assignment problem

来源：评论

学校读者我要写书评

暂无评论

Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems

引用

JOURNAL OF HEURISTICS 2008年第2期14卷 169-181页

作者： Gutin, Gregory Goldengorin, Boris Huang, Jing Univ London Royal Holloway & Bedford New Coll Dept Comp Sci Egham TW20 0EX Surrey England Univ Haifa Dept Comp Sci IL-31999 Haifa Israel Univ Groningen Dept Econ & Operat Res NL-9700 AV Groningen Netherlands Khmelnitsky Natl Univ Dept Appl Math Khmelnitsky Ukraine Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman (Oper. Res. 39:150-161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s >= 3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic (for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for the s-dimensional (s >= 3) assignment problem.

关键词： traveling salesman problem multidimensional assignment problem greedy heuristics domination analysis

来源：评论

学校读者我要写书评

暂无评论

Scalable Feature Matching Across Large Data Collections

引用

JOURNAL OF COMPUTATIONAL AND GRAPHICAL STATISTICS 2023年第1期32卷 196-212页

作者： Degras, David Univ Massachusetts Dept Math Boston MA 02125 USA

This article is concerned with matching feature vectors in a one-to-one fashion across large collections of datasets. Formulating this task as a multidimensional assignment problem with decomposable costs (MDADC), we develop fast algorithms with time complexity roughly linear in the number n of datasets and space complexity a small fraction of the data size. These remarkable properties hinge on using the squared Euclidean distance as dissimilarity function, which can reduce (2) matching problems between pairs of datasets to n problems and enable calculating assignment costs on the fly. To our knowledge, no other method applicable to the MDADC possesses these linear scaling and low-storage properties necessary to large-scale applications. In numerical experiments, the novel algorithms outperform competing methods and show excellent computational and optimization performances. An application of feature matching to a large neuroimaging database is presented. The algorithms of this article are implemented in the R package match Feat available at ***/ddegras/rnatchFeat. Supplementary materials for this article are available online.

关键词： Combinatorial optimization Constrained clustering multidimensional assignment problem

来源：评论

学校读者我要写书评

暂无评论

A bi-criteria approach for the data association problem

引用

ANNALS OF OPERATIONS RESEARCH 2006年第1期147卷 217-234页

作者： Hugot, Hadrien Vanderpooten, Daniel Vanpeperstraete, Jean Michel Univ Paris 09 LAMSADE F-75775 Paris 16 France Thales Airborne Syst F-78852 Elancourt France

The data association problem consists of associating pieces of information emanating from different sources in order to obtain a better description of the situation under study. This problem arises, in particular, when, considering several sensors, we aim at associating the measures corresponding to a same target. This problem, widely studied in the literature, is often stated as a multidimensional assignment problem where a state criterion is optimized. While this approach seems satisfactory in simple situations where the risk of confusing targets is relatively low, it is much more difficult to get a correct description in denser situations. This is why, we propose, for the first time to our knowledge, to address this problem in a multiple criteria framework using a second complementary criterion, based on the identification of the targets. Due to the specificities of the problem, simple and efficient approaches can be used to generate non-dominated solutions. Moreover, we show that the accuracy of the proposed solutions is greatly increased when considering a second criterion. A bi-criteria interactive procedure is also introduced to assist an operator in solving conflicting situations.

关键词： data association bi-criteria optimization multidimensional assignment problem interactive procedure

来源：评论

学校读者我要写书评

暂无评论

Random MHT Data Association Algorithm Based on Random Coefficient Kalman Filter 20

Random MHT Data Association Algorithm Based on Random Coeffi...

引用

20th International Conference on Information Fusion (Fusion)

作者： Zhang, Yi Shen, Xiaojing Wang, Zhiguo Zhu, Yunmin Sichuan Univ Sch Math Chengdu 610064 Sichuan Peoples R China

ISBN: (纸本)9780996452700

A novel random data association algorithm is proposed in the framework of multiple hypothesis tracking which can be equivalent to an NP-hard multidimensional assignment problem. The key idea of this new algorithm is to relax the multidimensional assignment problem to a linear programming problem. The solution of the linear programming problem may be treated as the probability of potential tracks, which avoids the computation difficulties of rounding the probability solution to 0/1 satisfying the constraints. Then all tracks and measurements can be integrated to a new whole dynamic system with random coefficient matrices. Moreover, the random coefficient matrix Kalman filtering is applied to the integrated dynamic system to derive the state estimates of the tracks. The significant advantage of the random Kalman filter-based multiple hypothesis tracking data association is that the computation complexity is much less than that of Lagrangian relaxation of the multidimensional assignment problem. Simulation demonstrates the random data association algorithm works well and the running time can be shortened greatly compared with the Lagrangian relaxation algorithm of the multidimensional assignment problem.

关键词： Multiple hypothesis tracking data association multidimensional assignment problem random coefficient matrices Kalman filter linear programming.

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：