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-di...
详细信息
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 assignmentproblem 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.
The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignmentproblem. Test problems of known solution are useful in exercising solution methods. A method of generati...
详细信息
The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignmentproblem. Test problems of known solution are useful in exercising solution methods. A method of generating an axial MAP of controllable size with a known unique solution is presented. Certain characteristics of the generated MAPs that determine realism and difficulty are investigated.
This work investigates two branch and bound algorithms based on different tree representations of the multidimensional assignment problem (MAP). The MAP may be depicted as either an index-based tree in which every lev...
详细信息
This work investigates two branch and bound algorithms based on different tree representations of the multidimensional assignment problem (MAP). The MAP may be depicted as either an index-based tree in which every level of the tree represents a different value of the first index or as a permutation-based tree that has vertices representing different permutation vectors of a feasible solution. We also look at the benefits of sorting the cost coefficients on each index tree level, performing a local search on either just the initial solution or every time we find a better solution, and attempting to use characteristics of previous good solutions through path relinking. The number of dimensions and the number of elements in each dimension will affect algorithm performance. We demonstrate the benefits and drawbacks of using different modifications to the branch and bound approach on different sizes of MAP instances.
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 cla...
详细信息
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 assignmentproblems, and many important problems in operations research and computer science can be formulated as assignmentproblems. This paper presents an overview of the recent results and developments in the area of probabilistic assignmentproblems, including the linear and multidimensional assignment problems, quadratic assignmentproblem, etc. (c) 2007 Elsevier B.V. All rights reserved.
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 nu...
详细信息
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) assignmentproblem.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. Randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. Randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
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, whe...
详细信息
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.
The multidimensional assignment problem ( MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and base...
详细信息
The multidimensional assignment problem ( MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.
We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignmentproblems and applications, multidimensional assignment problems, quadratic assignmentproblems, in pa...
详细信息
We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignmentproblems and applications, multidimensional assignment problems, quadratic assignmentproblems, in particular lower bounds, special cases and asymptotic results, biquadratic and communication assignmentproblems. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论