Publication Date:
2020-08-05
Description:
The analysis of random instances of a combinatorial optimization problem, especially their optimal values, can provide a better insight into its structure. Such an extensive analysis was theoretically and practically done for the assignment problem ("random assignment problem") and several of its generalizations.
For a recent generalization of the assignment problem to bipartite hypergraphs, the hypergraph assignment problem, such results do not exist so far. We consider a random version of the hypergraph assignment problem for the simplest possible complete bipartite hypergraphs. They have only edges and proper hyperedges of size four and follow a special structure, but the hypergraph assignment problem for this type of hypergraphs is, however, already NP-hard. It can be viewed as a combination of two assignment problems.
For random hyperedge costs exponentially i.i.d. with mean 1 we show computational results that suggest that the expected value of minimum cost hyperassignments converges to some value around 1.05 with a small standard deviation. The computational results also suggest that the optimal value is most probably attained with half of the maximum possible number of proper hyperedges.
The main result of this paper is the proof that the expected value of a minimum cost hyperassignment which uses exactly half the possible maximum number of proper hyperedges if the vertex number tends to infinity lies between 0.3718 and 1.8310 when hyperedge costs are exponentially i.i.d. with mean 1.
Language:
English
Type:
conferenceobject
,
doc-type:conferenceObject
Permalink
