Publications
]
(1986). A family of simplex variants solving an m*d linear program in expected number of pivot steps depending on d only.
Mathematics of Operations Research. 11(4), 570-590.
(1986). FED bin packing for item sizes with distributions on (0,1/2).
Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 322-330.
(1986). On a Search Problem Related to Branch-and-Bound Procedures.
Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 19-28.
(1985). The complexity of parallel computation.
Proceedings of the 23rd Annual Allerton Conference on Communication, Control, and Computing. 1.
(1985). A fast parallel algorithm for the maximal independent set problem.
Journal of the Association for Computing Machinery. 32(4), 762-773.
(1985). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Journal of Complexity. 1,
(1985). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Proceedings of the Symposium on the Complexity of Approximately Solved Problems. 45-64.
(1983). Global Wire Routing in Two-Dimensional Arrays.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 453-459.
(1983). Monte-Carlo Algorithms for Enumeration and Reliability Problems.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 56-64.
(1983). Searching for an optimal path in a tree with random costs.
Artificial Intelligence. 21(1-2), 99-116.
(1982). Dynamic Programming Meets the Principle of Inclusion and Exclusion.
Operations Research Letters. 1(2), 49-51.
(1982). An efficient approximation scheme for the one-dimensional bin-packing problem.
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. 312-320.
(1982). On Linear Characterizations of Combinatorial Optimization Problems.
SIAM Journal on Computing. 11(4), 620-632.
(1982). On the security of ping-pong protocols.
55(1-3), 57-68.
(1981). The Complexity of Testing Whether a Graph is a Superconcentrator.
13(4-5), 164-167.
(1981). Maximum Matchings in Sparse Random Graphs.
Proceedings of the 22nd IEEE Annual Symposium on Foundations of Computer Science. 364-375.
(1981). Parametric Shortest Path Algorithms with an Application to Cyclic Staffing.
Discrete Applied Mathematics (Netherlands). 3(1), 37-45.
(1980). An Algorithm to Solve the m*n Assignment Problem in Expected Time O(mn log n)*.
10(2), 143-152.
(1980). On Linear Characterizations of Combinatorial Optimization Problems.
Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. 1-9.
(1979). A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem.
SIAM Journal on Computing. 8(4), 561-573.
(1979). Probabilistic Analysis of Graph-theoretic Algorithms.
Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface.
(1979). Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems.
Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface. 174-176.
(1979). Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems.
Proceedings of the 20th Annual IEEE Symposium of Foundations of Computer Science. 218-223.