On the expected optimal value of random assignment problems: Experimental results and open questions

In the paper, we study the expected optimal value of random linear assignment problems, whose data are random variables with the uniform and the exponential distributions. An interior point approach is used to solve large-scale dense assignment problems with size up to 10,000 nodes and 100 million edges. Our computational results indicate the validity of a long-standing conjecture about the limiting value of the expected optimal assignment. Some interesting open problems and extensions are discussed.     

Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distributions the limiting value of the expected optimal cost of the MAP is determined by the location of the left endpoint of the support set of the distribution, and construct asymptotical bounds for the expected optimal cost.     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

Geometric algorithms for the minimum cost assignment problem

We consider the minimum-cost λ-assignment problem, which is equivalent to the minimum-weight one-to-many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ? k), respectively. Formulating the problem geometrically, we given an O(kn + k^2.5n^0.5 log^1.5 n) time randomized algorithm, which is better than the existing O(kn² + n² log n) time algorithm if n > k log k.     

On the expected value of stochastic linear programs and (dynamic) network flow problems

Using the n-dimensional Jensen inequality and a new integer version of it we develop a theory to compute bounds for stochastic linear programs. The probabilistic data can be right-hand side, cost, or—in the case of dynamic network flow problems—entries in the coefficient matrix.     

OPTIMAL REINSURANCE UNDER EXPECTED VALUE PRINCIPLE

The paper concerns the problem how to purchase the reinsurance in order to make the insurer and the reinsurance company＇s total risk to be least under the expected value principle. When the insurer and reinsurance company take arbitrary risk measures, sufficient con- ditions for optimality of reinsurance contract are given within the restricted class of admissible contracts. Further, the explicit forms of optimal reinsurance contract under several special risk measures are given, and the method to decide parameters as well.     

The expected value of the line integral of one-forms

The classic definition of line integral of one-forms does not apply when the line is not smooth.In this article it is analyzed from the point of view of measure theory, the problem of approximating a line integral using the quotient of Newton instead of the derivative.The expected value of a certain scheme of approximation of line integrals of closed one-forms, with respect to the Wiener measure, is computed. In particular, if a form is harmonic, then the expected value of the line integral is Zero.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

New scaling algorithms for the assignment and minimum mean cycle problems

In this paper we suggest new scaling algorithms for the assignment and minimum mean cycle problems. Our assignment algorithm is based on applying scaling to a hybrid version of the recentauction algorithm of Bertsekas and the successive shortest path algorithm. The algorithm proceeds by relaxing the optimality conditions, and the amount of relaxation is successively reduced to zero. On a network with 2n nodes,m arcs, and integer arc costs bounded byC, the algorithm runs in O( m log(nC)) time and uses very simple data structures. This time bound is comparable to the time taken by Gabow and Tarjan's scaling algorithm, and is better than all other time bounds under thesimilarity assumption, i.e.,C = O(n ^k ) for somek. We next consider the minimum mean cycle problem. Themean cost of a cycle is defined as the cost of the cycle divided by the number of arcs it contains. Theminimum mean cycle problem is to identify a cycle whose mean cost is minimum. We show that by using ideas of the assignment algorithm in an approximate binary search procedure, the minimum mean cycle problem can also be solved in O( m lognC) time. Under the similarity assumption, this is the best available time bound to solve the minimum mean cycle problem.     

An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns

Daily, there are multiple situations where machines or workers must execute certain jobs. During a working day it may be that some workers or machines are not available to perform their activities during some time periods. When scheduling models are used in these situations, workers or machines are simply called “machines”, and the temporal absences of availability are known as “breakdowns”. This paper considers some of these cases studying stochastic scheduling models with several machines to perform activities. Machines are specialized and models are flow-shops where breakdowns are allowed. The paper proposes a general procedure that tries to solve these problems. The proposed approach converts breakdowns scheduling problems into a finite sequence of without-breakdowns problems. Thus, we consider random variables, which measure the length of availability periods and repair times, to study availability intervals of machines. We propose partial feasible schedules in these intervals and combine them to offer a final global solution to optimize the expected makespan. Computational experiences are also reported.     

The Shapley value as the maximizer of expected Nash welfare

We provide an alternative interpretation of the Shapley value in TU games as the unique maximizer of expected Nash welfare.     

The bidding selection and assignment problem with minimum quantity commitment

This paper studies the bidding selection and assignment problem with a novel constraint, namely minimum quantity commitment (MQC), motivated by the Royal Philips Electronics Company. Responding to the stipulations by the US Federal Maritime Commission, any shipping agent transporting to the US must satisfy a minimum quantity of containers. To insure this MQC for shipping agents, the Royal Philips Electronics Company, with a large number of shipping needs, has to assign enough containers to each selected shipping agent to transport cargos to the US. This restriction creates difficulties for Philips as the company seeks to satisfy its shipping needs with minimum total costs. To solve this problem, we first formulate it by a mixed-integer programming model. In order for both linear programming relaxation and Lagrangian relaxation to provide good lower bounds, we then strengthen the model by a few valid inequalities. Furthermore, a Lagrangian-based heuristic and a branch and cut solver are applied to solve the problem. Extensive experiments show the effectiveness of all the models and methods.     

On the bottleneck assignment problem

In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.This work was carried out by the junior author while holding a Purdue University Fellowship.     

On the truncated assignment polytope

We investigate the convex polytope Ω_m,n(r) which is the convex hull of the m × nr-subpermutation matrices. The faces of Ω_m,n(r) are characterized, and formulae are obtained to compute their dimensions. The faces of Ω_m,n(r) are themselves convex polytopes, and we determine their facets.     

A note on the minimum instantaneous cost path of the dynamic traffic assignment problem

We consider an example to show that the minimum instantaneous cost path principle, as suggested in Friesz et al. [1] for generalising Wardrop's first principle to the dynamic state, may cause some drivers' routes to loop. These looping routes traverse the same link more than once - indeed, in our example six times.The work reported in this paper has been partly funded by the Science and Engineering Research Council of the United Kingdom.