Publications
Probabilistic Behavior of a Naive Coloring Algorithm on Random Graphs.
Bulletin of the Operations Research Society of America. 23,
(1975). Probabilistic Analysis of Partitioning Algorithms for the Traveling-salesman Problem in the Plane.
Mathematics of Operations Research. 2(3), 209-224.
(1977). Probabilistic analysis of network flow algorithms.
Mathematics of Operations Research. 18(1), 71-97.
(1993). Probabilistic Analysis of Linear Programming Decoding.
IEEE Transactions on Information Theory. 54(8), 3565-3578.
(2008). On the Price of Heterogeneity in Parallel Systems.
Theory of Computing Systems. 45(2), 280-301.
(2009). Prediction of Phenotype Information from Genotype Data.
Communications in Information and Systems. 10(2), 99-114.
(2010). On the power of randomization in on-line algorithms.
Algorithmica. 11(1), 2-14.
(1994). A Phenomenon in the Theory of Sorting.
Journal of Computer and System Sciences. 6(2), 103-115.
(1972). Pedigree Reconstruction Using Identity by Descent.
Journal of Computational Biology. 18(11), 1481-1493.
(2011). A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem.
SIAM Journal on Computing. 8(4), 561-573.
(1979). Parametric Shortest Path Algorithms with an Application to Cyclic Staffing.
Discrete Applied Mathematics (Netherlands). 3(1), 37-45.
(1981). Parallel Sorting with Limited Bandwidth.
29(6), 1997-2015.
(2000).
(1998). On the Optimality of Huffman Trees.
SIAM Journal on Applied Mathematics. 31(2), 368-378.
(1976). An Optimal Algorithm for Monte-Carlo Estimation.
29(5), 1484-1496.
(2000).
(2000). Near-optimal Solutions to a 2-dimensional Placement Problem.
SIAM Journal on Computing. 4(3), 271-286.
(1975). An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs.
SIAM Journal on Computing. 2(4), 225-231.
(1973). Monte-Carlo approximation algorithms for enumeration problems.
Journal of Algorithms. 10(3), 429-448.
(1989). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Journal of Complexity. 1,
(1985). A Monte-Carlo algorithm for estimating the permanent.
SIAM Journal on Computing. 22(2), 284-293.
(1993). The Minimum-Entropy Set Cover Problem.
Theoretical Computer Science. 348(2), 240-250.
(2005). A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica. 16(4-5), 543-547.
(1996). LogP: towards a realistic model of parallel computation.
SIGPLAN Notices. 28,
(1993). LogP: A Practical Model of Parallel Computation.
Communications of the ACM. 39(11), 78-85.
(1996).