Efficient algorithms for three‐dimensional axial and planar random assignment problems

DOI10.1002/RSA.20525MaRDI QIDQ5175234zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Gregory B. Sorkin, Alan Frieze

Publication date 20 February 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.0390, http://eprints.lse.ac.uk/61800/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Sorkin%2C%20G_Sorkin_Efficient%20algorithms_2015_author.pdf

zbMATH Keywords

algorithmsaverage-case analysisprobabilistic analysisrandom assignment problems

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Special processes (60K99) Discrete location and assignment (90B80)

Abstract: Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural "Axial" and "Planar" versions, both of which are NP-hard. For 3-dimensional Axial random assignment instances of size $n$, the cost scales as $Omega(1/n)$, and a main result of the present paper is a linear-time algorithm that, with high probability, finds a solution of cost $O(n^{-1+o(1)})$. For 3-dimensional Planar assignment, the lower bound is $Omega(n)$, and we give a new efficient matching-based algorithm that with high probability returns a solution with cost $O(nlogn)$.

Recommendations

• scientific article; zbMATH DE number 151870
• An algorithm for the planar three-index assignment problem
• Approximation algorithms for three-dimensional assignment problems with triangle inequalities
• On Asymptotically Optimal Algorithm for One Modification of Planar 3-dimensional Assignment Problem
• Axial three-index assignment and traveling salesman problems: fast approximate algorithms and their probabilistic analysis
• Randomized Approximation Algorithm for a Geometrical Multidimensional Assignment Problem
• Three-dimensional axial assignment problems with decomposable cost coefficients
• scientific article; zbMATH DE number 4131951
• Application of graph-theoretic approaches to the random landscapes of the three-dimensional assignment problem

Cites work

• A proof of Parisi's conjecture on the random assignment problem
• Algorithm and Average-value Bounds for Assignment Problems
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Assignment Problems
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Asymptotics in the random assignment problem
• Complexity of a 3-dimensional assignment problem
• Component structure in the evolution of random hypergraphs
• Constructive bounds and exact expectations for the random assignment problem
• Factors in random graphs
• Investigation of polynomial algorithms for solving the multicriteria three-index planar assignment problem
• On linear programs with random costs
• On the expected value of the minimum assignment
• On the value of a random minimum spanning tree problem
• Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• The (2) limit in the random assignment problem

Cited in

(10)

• On resource placements in 3D tori.
• The constant objective value property for multidimensional assignment problems
• Three-dimensional axial assignment problems with decomposable cost coefficients
• Thresholds versus fractional expectation-thresholds
• On random multi-dimensional assignment problems
• Perfect fractional matchings in \(k\)-out hypergraphs
• Algorithms for three-dimensional dominance searching in linear space.
• On Asymptotically Optimal Algorithm for One Modification of Planar 3-dimensional Assignment Problem
• A new efficiently solvable special case of the three-dimensional axial bottleneck assignment problem
• Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model

This page was built for publication: Efficient algorithms for three‐dimensional axial and planar random assignment problems

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