DRDavid P. Robbins

David P. Robbins

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


David P. Robbins has a total of 3 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • On the expected value of the minimum assignment

    by Marshall W. Buck, Clara S. Chan, David P. Robbins

    The minimum k‐assignment of an m × n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. Coppersmith and Sorkin conjectured that if X is generated by choosing each entry independently from the exponential distribution with mean 1, then the expected value of its minimum k‐assignment is given by an explicit formula, which has been proven only in a few cases. In this paper we describe our efforts to prove the Coppersmith–Sorkin conjecture by considering the more general situation where the entries xij of X are chosen independently from different distributions. In particular, we require that xij be chosen from the exponential distribution with mean 1/ricj. We conjecture an explicit formula for the expected value of the minimum k‐assignment of such X and give evidence for this formula. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 33–58, 2002


  • Open Access

    On the expected value of the minimum assignment

    by Marshall W. Buck, Clara S. Chan, David P. Robbins

    The minimum k-assignment of an m by n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. If X is generated by choosing each entry independently from the exponential distribution with mean 1, then Coppersmith and Sorkin conjectured that the expected value of its minimum k-assignment is \sum_{i,j \ge 0, i+j<k} 1/((m-i)(n-j)) and they (with Alm) have proven this for k < 5 and in certain cases when k=5 or k=6. They were motivated by the special case of k=m=n, where the expected value was conjectured by Parisi to be \sum_{i=1}^k 1/(i^2). In this paper we describe our efforts to prove the Coppersmith-Sorkin conjecture. We give evidence for the following stronger conjecture, which generalizes theirs. Conjecture. Suppose that r_1,...,r_m and c_1,...,c_n are positive real numbers. Let X be a random m by n matrix in which entry x_{ij} is chosen independently from the exponential distribution with mean 1/(r_ic_j). Then the expected value of the minimum k-assignment of X is \sum_{I,J} (-1)^{k - 1 - |I| - |J|} \binom{m + n - 1 - |I| - |J|}{k - 1 - |I| - |J|}\frac{1}{(\sum_{i \notin I}r_i) (\sum_{j \notin J} c_j)}. Here the sum is over proper subsets I of {1,...,m} and J of {1,...,n} whose cardinalities |I| and |J| satisfy |I|+|J|<k.

  • On the Volume of a Certain Polytope

    by Clara S. Chan, David P. Robbins, David S. Yuen

    Let n ≥ 2 be an integer and consider the set Tn of n × n permu tation matrices π for wh ich π ij = 0 for j ≥ i + 2. We study the convex hull Pn of Tn, a polytope of dimension (n 2). We provide evidence for several conjectures involving Pn, including Conjecture 1: Let Vn denote the minimum volume of a simplex with vertices in the affine lattice spanned by Tn. Then the volume of Pn is Vn time s the product of the first n – 1 Catalan numbers. We also give a related result on the Ehrhart polynomial of Pn. Editor's note: After this paper was circulated, Doron Zeilberger [1998] proved Conjecture 1, using the authors' reduction of the original problem to a conjectural comb inatorial identity, and sketched the proofs of two others. The problems and methodology presented here gain even further interest thereby.


  • On the Volume of the Polytope of Doubly Stochastic Matrices

    by Clara S. Chan, David P. Robbins

    We study the calculation of the volume of the polytope Bn of n × n doubly stochastic matrices (real nonnegative matrices with row and column sums equal to one). We describe two methods. The first involves a decompos ition of the polytope into simplices. The second involves the enumeration of “magic squares”, that is, n × n nonnegative integer matrices whose rows and columns all sum to the same integer. We have used the first method to confirm the previously known values through n = 7. This method can also be used to compute the volumes of faces of Bn For example, we have observed that the volume of a particular face of Bn appears to be a product of Catalan numbers. We have used the second method to find the volume for n = 8, which we believe was not previously known.