David P. Robbins
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
Research Subjects
David P. Robbins has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Clara S. Chan
Center for Communications Research, Princeton, NJ 08540
4 shared publications - Marshall W. Buck
Center for Communications Research 805 Bunn Dr. 2706 Post Oak Ct. 08540 21401 Princeton Annapolis NJ MD
2 shared publications - David S. Yuen
Math/CS Department, Lake Forest College, 555 N. Sheridan Rd., Lake Forest, IL 60045
1 shared publication
Latest Publications
- 27 June 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (1) , 33-58
On the expected value of the minimum assignment
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
- 27 June 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (1) , 33-58
On the expected value of the minimum assignment
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
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.
Open AccessOn the expected value of the minimum assignment
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.
- 1 January 2000
- Published by Taylor & Francis in Experimental Mathematics
- Vol. 9 (1) , 91-99
On the Volume of a Certain Polytope
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.
- 1 January 2000
- Published by Taylor & Francis in Experimental Mathematics
- Vol. 9 (1) , 91-99
On the Volume of a Certain Polytope
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.
- 1 January 1999
- Published by Taylor & Francis in Experimental Mathematics
- Vol. 8 (3) , 291-300
On the Volume of the Polytope of Doubly Stochastic Matrices
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.
- 1 January 1999
- Published by Taylor & Francis in Experimental Mathematics
- Vol. 8 (3) , 291-300
On the Volume of the Polytope of Doubly Stochastic Matrices
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.