**Friday, 11:30 - 11:55 h, Room: H 0110**

**Paul Krokhmal**

Asymptotic properties of random multidimensional assignment problems

**Abstract:**

We consider a class of discrete optimization problems where the underlying combinatorial structure is based on hypergraph matchings, which generalize the well-known problems on bipartite graph matchings, such as the Linear and Quadratic Assignment Problems, and are also known as multidimensional assignment problems (MAPs). Properties of large-scale randomized instances of MAPs are studied under assumption that their assignment costs are iid random variables. In particular, we consider linear and quadratic problems with sum and bottleneck objectives. For a broad class of probability distributions, we demonstrate strong convergence properties of optimal values of random MAPs as problem size increases. The analysis allows for identifying a subset of the feasible region containing high-quality solutions. We also investigate the average-case behavior of Linear Sum MAP in the case when the assumption regarding independence of the assignment costs is relaxed, and a correlation structure is present in the array of assignment costs. In particular, we consider the case of LSMAP with decomposable assignment costs.

Talk 3 of the invited session Fri.1.H 0110

**"Recent advances in nonconvex quadratic programming with random data"** [...]

Cluster 9

**"Global optimization"** [...]