The Random Hypergraph Assignment Problem

Abstract

Parisi’s famous (proven) conjecture states that the expected cost of an optimal assignment in a complete bipartite graph on n + n nodes with i. i. d. exponential edge costs with mean 1 is Sum (1/i2), which converges to an asymptotic limit of Pi2/6 as n tends to infinity. We consider a generalization of this question to complete “partitioned” bipartite hypergraphs G2;n that contain edges of size two and proper hyperedges of size four. We conjecture that for i. i. d. uniform hyperedge costs on [0; 1] and i. i. d. exponential hyperedge costs with mean 1, optimal assignments expectedly contain half of the maximum possible number of proper hyperedges. We prove that under the assumption of this number of proper hyperedges the asymptotic expected minimum cost of a hyperassignment lies between 0.3718 and 1.8310 if hyperedge costs are i. i. d. exponential random variables with mean 1. We also consider an application-inspired cost function which favors proper hyperedges over edges by means of an edge penalty parameter p. We show how results for an arbitrary p can be deduced from results for p = 0.