On optimality of a polynomial algorithm for random linear multidimensional assignment problem

DOI10.1007/s11590-010-0198-6zbMath1213.90158OpenAlexW2019511671MaRDI QIDQ628662

Pavlo A. Krokhmal

Publication date: 14 March 2011

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-010-0198-6

zbMATH Keywords

greedy heuristicapproximabilityconvergence almost surely

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Related Items (2)

Exact solution approaches for bilevel assignment problems ⋮ Multidimensional assignment problem for multipartite entity resolution

Cites Work

• Approximation algorithms for three-dimensional assignment problems with triangle inequalities
• Selected topics on assignment problems
• Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Random assignment problems
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems
• Solving the multisensor data association problem.
• The asymptotic probabilistic behaviour of quadratic sum assignment problems
• An Algorithm for the Three-Index Assignment Problem
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• Letter to the Editor—The Multidimensional Assignment Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On optimality of a polynomial algorithm for random linear multidimensional assignment problem