Printer Friendly

The random hypergraph assignment problem.

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 [[SIGMA].sup.n.sub.i=1] 1/[i.sup.2], which converges to an asymptotic limit of [[pi].sup.2]/6 as n tends to infinity. We consider a generalization of this question to complete "partitioned" bipartite hypergraphs [G.sub.2,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.

Keywords: assignment, hyperassignment, random, expected value

Povzetek: V clanku je opisana analiza komplektnosti dvojno povezanih grafov na osnovi razsiritve Parisijevega izreka.

1 Introduction

A way to gain a better understanding of the structure of a combinatorial optimization problem is to analyze the optimal values of random instances. For the assignment problem, such results were conjectured after extensive computational experiments and then proven theoretically. In particular, the famous (proven) Conjectures of Mezard and Parisi [Mezard and Parisi, 1985] state that the expected optimal cost value of an assignment problem on a complete bipartite graph with i. i. d. uniform edge costs on [0,1] or i.i.d. exponential edge costs with mean 1 converges to [[pi].sup.2]/6 = 1.6449 ... if the number of vertices tends to infinity. The limit is equal for both distributions since it can be proven that only the density at 0 is relevant, which coincides for both distributions [Aldous, 1992]. For a survey on the random assignment problem and several of its variants, see [Krokhmal and Pardalos, 2009].

We consider a generalization of this setting to a class of bipartite hypergraphs in terms of what we call the random hypergraph assignment problem (HAP). This problem is an idealized version of vehicle rotation planning problems in long-distance passenger rail transport, see [Borndorfer et al., 2011] for further details and [Maroti, 2006] for a survey on railway vehicle rotation planning.

We will deal with HAPs in a special well-structured type of bipartite hypergraphs [G.sub.2,n], that contain on each side n "parts" of size 2 each. In this case, the HAP is already NP-hard [Borndorfer and Heismann, 2012] and therefore interesting to analyze. The hyperedge set of such a partitioned hypergraph [G.sub.2,n] consists only of edges of size 2 and proper hyperedges of size 4, and it has a structure that makes it easy to view a hyperassignment as a combination of two assignments, one consisting only of edges, and the other one consisting only of proper hyperedges (that can also be viewed as edges). Despite this simple general idea, however, combining the two assignments involves a choice over an exponential number of possibilities which is quite difficult to analyze. We will explain this in more detail in Section 2 after introducing the problem.

In Section 3, we conjecture that the expected number of proper hyperedges in an optimal solution of the random HAP on partitioned hypergraphs [G.sub.2,2n] with i. i. d. uniform random edge costs on [0,1] or i. i. d. exponential random edge costs with mean 1 is n. This conjecture is based on extensive computational results. Assuming that this conjecture holds, we can prove a lower bound of 0.3718 and an upper bound of 1.8310 for the expected value of a minimum cost hyperassignment in [G.sub.2,2n] for the exponential edge cost distribution and for vertex numbers tending to infinity. To achieve this, we first use a combinatorial argument to represent the bounds in terms of bounds for random assignments. Then, we compute these bounds using results for the random assignment problem.

In hypergraph assignment problems that arise from practical applications, proper hyperedges represent unions of edges. Such hyperedges have costs that are smaller than the sum of the costs of the edges that they contain; these edges are considered to be similar and a solution with much similarity is desirable [Borndorfer et al., 2011], We consider a setting with regularity-rewarding cost functions, in which the number of proper hyperedges in a solution and the optimal value of a random HAP in [G.sub.2,n] do not only depend on the number of vertices n but also on an edge penalty parameter p. We will show how the number of proper hyperedges and the value of an optimal solution for every p can be deduced from results for p = 0 in Section 4.

The paper ends in Section 5 with a discussion of the results.

A short conference version of this paper has already been published as [Heismann and Borndorfer, 2013].

2 The hypergraph assignment problem

We consider in this paper hypergraph assignment problems on a special type of bipartite hypergraphs.

Definition 2.1. Let [G.sub.2,n] = (U, V, E) be the bipartite hypergraph with vertex sets

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with

[U.sub.i] = {[u.sub.i], [u'.sub.i]}, [V.sub.i] = {[[upsilon].sub.i], [[upsilon]'.sub.i]}

and hyperedge set E = [E.sub.1] [union] [E.sub.2] where

[E.sub.1] = {{u, [upsilon]} : u [member of] U, [upsilon] [member of] V}

are the edges and

[E.sub.2] = {[U.sub.i] [union] [V.sub.j] : i, j [member of] {1, ..., n}}

are the proper hyperedges of size 4. The sets [U.sub.i] and [V.sub.i], i [member of] {1, ..., n} are called the parts on the U- and V-side, respectively.

For a visualization of such a hypergraph, see Figure 1.

Note that every hyperedge in [G.sub.2,n] connects a part on the U- and a part on the V-side. We remark that the HAP can be formulated in the same way for more general bipartite hypergraphs, with less structure and possibly containing hyperedges which contain more than four vertices, see [Borndorfer and Heismann, 2012].

Definition 2.2. For a vertex subset W [subset or equal to] U [union] V we define the incident hyperedges

[delta](W) := {e [member of] E : e [intersection] W [not equal to] [empty set], e \ W [not equal to] [empty set]}

to be the set of all hyperedges having at least one vertex in both W and (U [union] V) \ W.

A hyperassignment in [G.sub.2,n] is a subset H [subset or equal to] E of pairwise disjoint hyperedges that cover U and V, i.e., for all [e.sub.1], [e.sub.2] [member of] H, [e.sub.1] [intersection] [e.sub.2] = [empty set], and [union]H = U [union] V. Given a cost function [c.sub.E] : E [right arrow] R, the cost of a hyperassignment is [[SIGMA]sub.e[member of]H] [c.sub.E](e). The hypergraph assignment problem with input ([G.sub.2,n], [c.sub.E]) consists of finding a hyperassignment in [G.sub.2,n] of minimum cost w. r. t. [c.sub.E].

For bipartite hypergraphs [G.sub.2,n], the hypergraph assignment problem can be seen as a combination of two assignment problems. Namely, observe that for every hyperassignment H and every part [U.sub.i] and [V.sub.i], i [member of] {1, ..., n}, the set of incident hyperedges [delta]([U.sub.i]) [intersection] H and [delta]([V.sub.i]) [intersection] H consists either of one proper hyperedge or of two edges. If we decide for every part [U.sub.i] and [V.sub.i] whether the hyperassignment to be constructed is incident to one proper hyperedge or to two edges, we can restrict the hyperedge set of [G.sub.2,n] to

--the set of edges connecting pairs of vertices from the parts [U.sub.i], [V.sub.i] that will be incident to edges--this is the first assignment problem, and

--the proper hyperedges {[U.sub.i] [union] [V.sub.i]} for [U.sub.i] and [V.sub.j] that will be incident to proper hyperedges--viewing [U.sub.i] and [V.sub.j] as composite vertices and the hyperedges as edges connecting them--this is the second assignment problem.

Solving these two assignment problems independently produces the minimum cost hyperassignment subject to the fixed edge and hyperedge incidences.

The HAP in [G.sub.2,n] can thus be solved in two steps. The first step decides which parts [U.sub.i] and [V.sub.i] will be incident to proper hyperedges. Of course, we must chose the same number of parts on the U- and the V-side, equal to the number of proper hyperedges in the hyperassignment to be constructed; the other parts will be incident to edges. The second steps consists of solving the resulting two assignment problems stated above.

3 Expected optimal values for the random HAP with exponential or uniform costs

Predicting the optimal value of a random hypergraph assignment problem in [G.sub.2,n] involves a prediction of the number of proper hyperedges in an optimal solution. This number depends on how advantageous it is to choose a proper hyperedge instead of two edges (so that one has just one number adding to the cost instead of two) compared to the disadvantage of having less freedom (there are fewer possibilities to cover a single vertex with a proper hyperedge than with an edge) when searching for a hyperassignment with the least possible cost. We conjecture that one can expect that an optimal hypergraph assignment in [G.sub.2,n] contains half of the possible number of proper hyperedges.

Conjecture 3.1. The expected number of proper hyperedges in a minimum cost hyperassignment in [G.sub.2,2n] with cost function [c.sub.E] such that all [c.sub.E] (e), e [member of] E are i. i.d. exponential random variables with mean 1 or i.i.d. uniform random variables on [0,1] is n.

Table 1 backs this conjecture. It gives computational results for the random hypergraph assignment problem in the bipartite hypergraph [G.sub.2,n] with i. i. d. uniform random variables on [0,1] and i. i. d. exponential random variables with mean 1 as hyperedge costs. For every n, we report the mean value and the standard deviation of the optimal cost value and the number of proper hyperedges in the optimal solution for 1000 computations. The HAPs were solved as integer programs using CPLEX 12.5.

The first column (n) of Table 1 shows the number of parts on the U- and C-side. Columns 2 and 6 (opt. val.) give the mean optimal values. Their standard deviations can be seen in columns 3 and 7 (s. d.) for the two cost function distributions, respectively. Columns 4 and 8 (# pr. hy.) show the number of proper hyperedges in the optimal solutions found, columns 5 and 9 (s. d.) show their standard deviations. The important finding w. r. t. Conjecture 3.1 is that the values in columns 4 and 8 are about half the values in column 1 in each row.

The computational results also suggest that the expected optimal cost converges to a value around 1.05 for both distributions. Although for larger n more hyperedges are contained in a hyperassignment, the optimal value does not increase much. This can be intuitively explained by noting that for larger n there are also more possible hyperassignments to select from, and the chances to find a hyperassignment that has a low cost are therefore still good even if it will contain more hyperedges.

We will now compute a lower and upper bound on the expected value of a minimum cost hyperassignment in [G.sub.2,2n] with n proper hyperedges for the exponential distribution. To this end, we will use the following result: For a complete bipartite graph with vertex sets of size m and n and with i. i. d. exponential random variables with mean 1 as edge costs, the expected minimum value of the sum of k pairwise disjoint edges (this is called a partial assignment) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This result was conjectured in

[Coppersmith and Sorkin, 1999] and first proved in [Linusson and Wastlund, 2004]. The latter paper also shows that for m = n = k this term can be written as

E (n, n, n) = [n.summatin over (i=1)] 1/[i.sup.2].

That this formula gives the expected value of a random assignment is Parisi's Conjecture.

Theorem 3.2. Let E be the expected value of the minimum cost of a hyperassignment in [G.sub.2,2n] = (U, V,E) with exactly n proper hyperedges and cost function ce with i. i. d. exponential random variables [c.sub.E](e) with mean 1 for all e [member of] E. The following holds for n [right arrow] [infinity]:

0.3718 < E < 1.8310.

Proof. By definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using E(n), we can bound the expected value of a hyperassignment in [G.sub.2,2n] with i. i. d. exponential random variables with mean 1 as hyperedge costs restricted to the hyperassignments with n proper hyperedges as follows.

For the lower bound, observe that in the best possible hyperassignment the selected n proper hyperedges can be only as good as the n pairwise disjoint proper hyperedges with the least possible cost sum in [G.sub.2,2n]. Also, the selected 2n edges can be only as good as the 2n pairwise disjoint edges with the least possible cost sum in [G.sub.2,2n]. Thus, E(n) + E(2n) is a lower bound for E.

On the other hand, choosing the n pairwise disjoint proper hyperedges with the least possible cost sum in [G.sub.2,2n] and finding the best possible edges for the remaining "unused" vertices leads to an upper bound of E(n) + E(2n, 2n, 2n) for E.

To transform the two-indexed sum describing E(n) to a sum with only one index, we calculate the difference D(n) := E(n + 1) - E(n) and use the recursive formula

E(n) = E(1) + [n-1.summation over (i=1)] D(i) = 1/4 + [n-1.summation over (i=1)] D(i). (1)

We get

D(n) = E(n + 1) E(n) = E (2n + 2,2n + 2,n + 1) E(2n, 2n, n)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Shifting the index of the first sum to get the same summand type in both sums yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We now split the sums to sums with index range i,j [greater than or equal to] 0, i + j [less than or equal to] n - 4 so that they can cancel. The remainder is as follows. For the first sum, it is used that it is symmetric in i and j. The term [4[(n + 3).sup.2]/4[(n + 1).sup.2][(2n + 1).sup.2]] is sum values where -2 [less than or equal to] i,j [less than or equal to] -1. This has to be subtracted from the first term as otherwise these values would be counted twice.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Splitting the first sum into two parts with i = -1 and i = -2 and substituting j by a - i where i + j = a yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the notation [H.sub.n] = [[SIGMA].sup.n.sub.i=1] 1/i the n-th harmonic number and partial fraction decomposition to get denominators linear in n for the last two summations, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally, simplification yields

D(n) = -([H.sub.2n] - [H.sub.n]). [9[n.sup.2] + 11n + 4/3(n + 1)(2n + 1)(3n + 1)(3n + 2)] + [8[n.sup.2] + 13n + 6/12[(n + 1).sup.2] [(2n + 1).sup.2] (3n + 2)].

To get bounds on E(n) using Equation (1), we first use that

[[infinity].summation over (n=1)] [8[n.sup.2] + 13n + 6/12[(n + 1).sup.2] [(2n + 1).sup.2] (3n + 2)] = - 1/4 - [pi]/[square root of ]3 + [[pi].sup.2]/9 - 10 ln(2)/3 + ln(27). (2)

Then, observe that [H.sub.2n] - [H.sub.n] is a non-negative number monotonically increasing with n. Also, this is an alternating harmonic number that for n [right arrow] [infinity] converges to ln(2). For n = 80, [H.sub.2n] - [H.sub.n] can be calculated and results in a fraction, which is > 0.69. Therefore, for n [greater than or equal to] 80,

0.69 < [H.sub.2n] - [H.sub.n] < ln(2) (3)

Now, computing the partial sum

[79.summation over (n=1)] - ([H.sub.2n] - [H.sub.n]) [9[n.sup.2] + 11n + 4/3(n + 1)(2n + 1)(3n + 1)(3n + 2)]

exactly and the limes

[[infinity].summation over (n=80)] - ([H.sub.2n] - [H.sub.n]) [9[n.sup.2] + 11n + 4/3(n + 1)(2n + 1)(3n + 1)(3n + 2)]

after substituting for [H.sub.2n] - [H.sub.n] the lower and upper bounds given by (3), Equations (1) and (2) yield

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, we get for the lower bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and for the upper bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We remark that the upper bound computed in Theorem 3.2 is greater than the expected optimal value of the random assignment problem [[pi].sup.2]/6 = 1.6449.... We believe that it must be possible to reduce it, because moving from an assignment problem in a complete bipartite graph with 4n vertices on each side to a HAP in [G.sub.2,2n] adds more possibilities (still all assignments are feasible solutions but using hyperassignments with proper hyperedges gives additional ones). Indeed, it is clear that if we do not prescribe the number of proper hyperedges in an optimal solution, the expected optimal value of a hyperassignment in [G.sub.2,2n] will tend to some number [less than or equal to] [[pi].sup.2]/6. As already discussed, the computational results shown in Table 1 suggest that the correct number is some value around 1.05, much smaller than [[pi].sup.2]/6.

4 Regularity rewarding costs

Hypergraph assignment problems arising from practical applications feature costs for proper hyperedges that depend on the costs of the edges that they contain. Indeed, proper hyperedges model a "reward" for choosing combinations of edges; in this way, one can model a so-called regularity of the solution [Borndorfer et al., 2011], More precisely, one considers partitioned bipartite hypergraphs and wants to favor the simultaneous choice of a set of edges that connects all nodes in a certain part in U to all nodes in a certain part in V. To this purpose, one introduces a proper hyperedge that represents the union of such pairwise disjoint edges and that has a cost that is smaller than the sum of the edge costs. If different edge combinations result in the same hyperedge, the cost is inferred from the edge set with the minimum cost sum. Here is a more formal statement.

Definition 4.1. Let G = (U, V, E) be a partitioned hypergraph. For e [member of] E, let

E(e) := {E' [subset or equal to] [E.sub.1] : [e.sub.1] [intersection] [e.sub.2] = [empty set] [for all][e.sub.1], [e.sub.2] [member of] E' with [e.sub.1] [not equal to] [e.sub.2], [union] E' = e}

be the set of all pairwise disjoint edge sets with union e.

For some penalty p [greater than or equal to] 0, we call a cost function [c.sup.p.sub.E]: E [right arrow] R regularity-rewarding if for all proper hyperedges e [member of] [E.sub.2],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The greater p, the more irregularity is punished and regularity rewarded. We remark that the cost of a hyperedge in a vehicle rotation planning model depends on several other parameters such as an additional irregularity penalty for hyperedges that are not inclusion-wise maximal [Borndorfer et al., 2011], This is the reason why we call p a penalty and not a bonus or a reward.

A way to define a regularity-rewarding random cost function [c.sup.p.sub.E] is to draw a random basic cost [r.sub.e] for each edge e [member of] [E.sub.1], e. g., from a uniform distribution on [0,1] or an exponential distribution with mean 1, and then to set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the following, we will assume that [c.sup.p.sub.E] is structured in this way with arbitrary [r.sub.e].

For a given bipartite hypergraph [G.sub.2,n] = (U, V, E) and random basic costs [r.sub.e] for the edges e [member of] [E.sub.1], we denote by z(h,p) the minimal cost value of a hyperassignment with penalty p that contains exactly 0 [less than or equal to] h [less than or equal to] n proper hyperedges.

Obviously, the number of proper hyperedges and the value of an optimal solution will depend on p. If p = 0, there is no reward for choosing a proper hyperedge. For every solution using proper hyperedges, we can find a solution with the same value that contains only edges by replacing each proper hyperedge {[u.sub.i], [u'.sub.i], [v.sub.j], [v'.sub.j]} by either the two edges {[u.sub.i], [v.sub.j]}, {[u'.sub.i], [v'.sub.j]} or the two edges {[u.sub.i], [v'.sub.j]}, {[u.sub.i], [v.sub.j]} depending on which two edges have the lower cost sum. On the other hand, if p is very large, choosing edges for a solution becomes so disadvantageous that the number of proper hyperedges in an optimal solution will become very high.

Fortunately, knowledge about the case p = 0 gives information about all other penalties as the following theorem shows. Thus, we do not need to analyze random HAPs for regularity-rewarding cost functions separately for each penalty p.

For some random basic cost distribution, we denote by Z(h) the expected value of z(h, 0) with respect to this distribution. Although z(h, 0) is defined only for integral h, we will view Z(h) as a continuous, monotonically increasing, differentiable function on [0, n]. This will allow us to formulate our result in a much easier way than if we would have to replace the derivative by its discretization. We can require Z(h) to be monotonically increasing, because z(h, 0) is monotonically increasing with increasing h. The reason is that, as described above, using proper hyperedges in the solution cannot lead to smaller optimal values than using only edges in the case p = 0.

Theorem 4.2. Consider the complete bipartite hypergraph [G.sub.2,n] = (U, V, E) and let [r.sub.e], e [member of] [E.sub.1] be random basic costs chosen from some random distribution. Denote by [h.sup.1.sub.d],... [h.sup.k.sub.d] the solutions to the equation Z'(h) = 2p and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then the expected number of proper hyperedges in an optimal solution to the HAP in [G.sub.2,n] w.r.t.[c.sup.p.sub.E] with basic random costs [r.sub.e] is h* and the expected optimal value of the random HAP is

Z(h*) - (2n - 2h*)p.

Proof. First, observe that

z(h, p) = z(h, 0) + (2n - 2h)p

holds since the cost of each hyperassignment H w. r. t. [c.sup.p.sub.E] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since this holds for all random basic costs, it also holds for the expected value of all random basic cost distributions and we get

E (z(h,p)) = Z(h) + (2 n - 2 h)p.

Its derivative is Z'(h) - 2p. A minimum of a differentiable function is attained either at the bounds or where the derivative is equal to zero, which proves the theorem.

5 Discussion

In this paper, we have presented results on the expected minimum cost of the random hypergraph assignment problem for two types of cost functions.

For the first type, i.i.d. exponential random variables with mean 1 or i.i.d. uniform random variables on [0,1], we conjectured that the number of proper hyperedges in an optimal solution is expected to be n for the hypergraph ([G.sub.2,2n], and showed computational results supporting this conjecture. Assuming this number of proper hyperedges in an optimal solution, we proved bounds on the expected optimal value for a vertex number tending to infinity. A proof of our conjecture as well as convergence results and either sharper bounds or an exact limit would be a natural continuation of our work towards a generalization of Mezard and Parisi's Conjecture. A first step is to extend the proof of our bounds to fixed numbers of hyperedges other than n by altering the computation.

For the second type of regularity-rewarding cost functions, we established a connection between results for different penalty values. This result could be extended by an analysis similar to that for the first cost function type in future.

All our results hold for complete partitioned hypergraphs [G.sub.2,n]. A further line of research could try to extend these results to bipartite hypergraphs with larger part sizes or even bipartite hypergraphs that are not partitioned or/and not complete.

Our results show how to approach the random FIAP using results for the random assignment problem. Probably approaches using more sophisticated probability-theoretical results are needed to understand more about the problem.

Ralf Borndorfer

Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany

E-mail: borndoerfer@zib.de

Olga Heismann

Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany

E-mail: heismann@zib.de

Received: July 13, 2014

References

[Aldous, 1992] Aldous, D. (1992). Asymptotics in the random assignment problem. Probability Theory and Related Fields, 93:507-534.

[Borndorfer and Heismann, 2012] Borndorfer, R. and Heismann, O. (2012). The hypergraph assignment problem. Technical Report 12-14, ZIB.

[Borndorfer et al., 2011] Borndorfer, R., Reuther, M, Schlechte, T., and Weider, S. (2011). A Hypergraph Model for Railway Vehicle Rotation Planning. In Caprara, A. and Kontogiannis, S., editors, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011), volume 20 of OpenAccess Series in Informatics (OASIcs), pages 146-155, Dagstuhl, Germany. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. ZIB Report 11-36.

[Coppersmith and Sorkin, 1999] Coppersmith, D. and Sorkin, G. B. (1999). Constructive bounds and exact expectations for the random assignment problem. Random Structures & Algorithms, 15(2): 113-144.

[Heismann and Borndorfer, 2013] Heismann, O. and Borndorfer, R. (2013). The random hypergraph assignment problem. In Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013.

[Krokhmal and Pardalos, 2009] Krokhmal, P. A. and Pardalos, P. M. (2009). Random assignment problems. European Journal of Operational Research, 194(1): 1-17.

[Linusson and Wastlund, 2004] Linusson, S. and Wastlund, J. (2004). A proof of Parisi's conjecture on the random assignment problem. Probability Theory and Related Fields, 128(3):419-440.

[Maroti, 2006] Maroti, G. (2006). Operations research models for railway rolling stock planning. PhD thesis, Technische Universiteit Eindhoven.

[Mezard and Parisi, 1985] Mezard, M. and Parisi, G. (1985). Replicas and optimization. Journal de Physique Lettres, 46:771-778.

Table 1: Computational results for random hypergraph assignment
problems in [G.sub.2,n] for i. i. d. uniform random variables on
[0,1] or i. i. d. exponential random variables with mean 1 as
hyperedge costs. The mean optimal values (column 2 and 6) and
their standard deviations (column 3 and 7) are rounded to the
third decimal place. The number of proper hyperedges in the
optimal hyperassignments (column 4 and 8) and their standard
deviations (column 5 and 9) are rounded to one decimal place.
1000 computations were done for each value of n and each
distribution. The values in columns 4 and 8 are about half
the value of column 1 in each row. This supports
Conjecture 3.1.

                   uniform on [0,1]

n      opt. val.   s. d.   # pr. hy.   s. d.

10     0.943       0.177   5.5         2.0
20     1.006       0.136   10.4        2.8
30     1.018       0.109   15.5        3.4
40     1.037       0.096   20.7        4.0
50     1.036       0.085   25.8        4.4
60     1.044       0.078   31.0        4.8
70     1.041       0.074   35.8        4.9
80     1.044       0.070   40.9        5.4
90     1.044       0.066   45.9        5.8
100    1.047       0.061   50.9        6.3
110    1.047       0.058   56.3        6.3
120    1.048       0.057   61.1        6.6
130    1.051       0.055   66.4        7.1
140    1.053       0.054   71.6        7.4
150    1.051       0.053   76.0        7.7
160    1.048       0.049   81.6        7.4

                   exponential
                   with mean 1

n      opt. val.   s.d.    # pr. hy.   s.d.

10     1.019       0.206   5.3         2.0
20     1.039       0.141   10.4        2.8
30     1.049       0.117   15.3        3.4
40     1.045       0.097   20.5        3.9
50     1.054       0.085   25.4        4.3
60     1.050       0.080   30.6        4.7
70     1.053       0.079   35.6        5.1
80     1.054       0.069   40.6        5.4
90     1.053       0.066   45.9        5.8
100    1.057       0.063   50.6        6.3
110    1.054       0.060   56.1        6.4
120    1.052       0.056   61.1        6.7
130    1.054       0.053   66.3        6.9
140    1.053       0.051   71.3        7.1
150    1.051       0.050   76.2        7.5
160    1.054       0.048   81.2        7.6
COPYRIGHT 2015 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Borndorfer, Ralf; Heismann, Olga
Publication:Informatica
Article Type:Report
Date:Sep 1, 2015
Words:5086
Previous Article:Barrier resilience of visibility polygons.
Next Article:Strategic deployment in graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters