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

DOI10.1007/S11590-010-0198-6zbMATH Open1213.90158OpenAlexW2019511671MaRDI QIDQ628662FDOQ628662

Authors: 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

Recommendations

• On random multi-dimensional assignment problems
• Asymptotic properties of random multidimensional assignment problems
• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Asymptotic results for random multidimensional assignment problems

zbMATH Keywords

greedy heuristicapproximabilityconvergence almost surely

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• A randomized polynomial-time simplex algorithm for linear programming
• Computational studies of randomized multidimensional assignment problems
• Exact solution approaches for bilevel assignment problems
• Polynomial algorithm for finding an asymptotically optimal solution to the multi-index planar choice problem.
• On random multi-dimensional assignment problems
• Multidimensional assignment problem for multipartite entity resolution
• On the probabilistic analysis of a decentralized version of one generalization of the assignment problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q628662)