On random multi-dimensional assignment problems

DOI10.1016/J.DAM.2020.07.013zbMATH Open1460.60115arXiv1901.07167OpenAlexW3046250074MaRDI QIDQ2004066FDOQ2004066

Wesley Pegden, Tomasz Tkocz, Alan Frieze

Publication date: 14 October 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study random multidimensional assignment problems where the costs decompose into the sum of independent random variables. In particular, in three dimensions, we assume that the costs $W_{i,j,k}$ satisfy $W_{i,j,k}=a_{i,j}+b_{i,k}+c_{j,k}$ where the $a_{i,j},b_{i,k},c_{j,k}$ are independent exponential rate 1 random variables. Our objective is to minimize the total cost and we show that w.h.p. a simple greedy algorithm is a $(3+o(1))$-approximation. This is in contrast to the case where the $W_{i,j,k}$ are independent exponential rate 1 random variables. Here all that is known is an $n^{o(1)}$-approximation, due to Frieze and Sorkin.

Full work available at URL: https://arxiv.org/abs/1901.07167

zbMATH Keywords

random assignment problemmulti-dimensional

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic programming (90C15) Special processes (60K99) Discrete location and assignment (90B80)

Cites Work

• An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
• A proof of Parisi's conjecture on the random assignment problem
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem
• Efficient algorithms for three‐dimensional axial and planar random assignment problems

Cited In (6)

• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
• Random assignment problems on \(2d\) manifolds
• A Probabilistic Approach to Solving Assignment Problems
• Title not available (Why is that?)
• Random assignments on sequentially dichotomous domains

This page was built for publication: On random multi-dimensional assignment problems

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