MIME-Version: 1.0
Server: CERN/3.0
Date: Wednesday, 2cp: No match.
:57 GMT
Content-Type: text/html
Content-Length: 8782
Last-Modified: Thursday, 10-Oct-96 00:17:32 GMT
Jon Kleinberg's Homepage
Jon Kleinberg
- kleinber@cs.cornell.edu
- Assistant Professor of Computer Science
- Cornell University
- Ithaca, NY 14853-7501
My research interests are in algorithms and combinatorial optimization,
with an emphasis on approximation, computational geometry,
network optimization and distributed computing, and
algorithms in molecular biology.
Recent work has included
approximation algorithms for routing and
disjoint paths problems in networks;
adversarial queueing theory, an approach to analyzing the stability
of network routing protocols without probabilistic assumptions;
geometric methods in combinatorial optimization, particularly
the use of positive semi-definite programming; and
geometric algorithms for studying molecular conformation.
I am spending the 1996-97 academic year visiting the
IBM Almaden
Research Center.
Click here to see
Approximation Algorithms and Combinatorial Optimization
J. Kleinberg. Single-source unsplittable flow.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.
J. Kleinberg, R. Rubinfeld. Short paths
in expander graphs.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.
J. Kleinberg, E. Tardos. Disjoint
paths in densely embedded graphs.
Proc. 36th IEEE Symposium on Foundations of Computer Science,
1995.
J. Kleinberg, E. Tardos. Approximations
for the disjoint paths problem in high-diameter planar networks.
Proc. 27th ACM Symposium on Theory of Computing, 1995.
A. Aggarwal, J. Kleinberg, D. Williamson. Node-disjoint
paths on the mesh, and a new trade-off in VLSI layout.
Proc. 28th ACM Symposium on Theory of Computing, 1995.
M. Goemans, J. Kleinberg. An improved
approximation ratio for the minimum latency problem.
Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.
J. Kleinberg, M. Goemans. The Lovasz theta
function and a semi-definite programming relaxation of vertex cover.
To appear in SIAM J. Discrete Math.
On-Line Algorithms
J. Kleinberg. The localization problem for
mobile robots. Proc. 35th IEEE Symposium on Foundations of Computer
Science, 1994.
J. Kleinberg. On-line search in a simple
polygon. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
J. Kleinberg. A lower bound for two-server
balancing algorithms. Information Processing Letters 51(1994).
R. El-Yaniv, J. Kleinberg. Geometric two-server
algorithms. Information Processing Letters 53(1995).
J. Kleinberg. On-line algorithms for robot
navigation and server problems. MIT/LCS/TR-641. (Master's Thesis.)
Parallel and Distributed Computing
D.M. Andrews, B. Awerbuch, A. Fernandez,
J. Kleinberg, F.T. Leighton, Z. Liu.
Universal stability results for greedy
contention-resolution protocols.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.
A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson.
Adversarial queueing theory.
Proc. 28th ACM Symposium on Theory of Computing, 1995.
J. Kleinberg, H. Attiya, N. Lynch. Trade-offs
between message delivery and quiesce times in connection management
protocols. Proc. 3rd Israel Symposium on Theory of Computing and Systems,
1995.
J. Kleinberg, S. Mullainathan. Resource bounds
and combinations of consensus objects. Proc. 12th ACM Symposium on
Principles of Distributed Computing, 1993.
Geometric Algorithms
B. Berger, J. Kleinberg, F.T. Leighton. Reconstructing a
Three-Dimensional Model with Arbitrary Errors.
Proc. 28th ACM Symposium on Theory of Computing, 1995.
D. Huttenlocher, J. Kleinberg. Comparing
point sets under projection. Proc. 5th ACM-SIAM Symposium on
Discrete Algorithms, 1994.
D. Huttenlocher, K. Kedem, J. Kleinberg. On
dynamic Voronoi diagrams and the minimum Hausdorff distance for point
sets under Euclidean motion in the plane. Proc. 8th ACM Symposium
on Computational Geometry, 1992.
D. Huttenlocher, J. Kleinberg, Invariants
of set of points or line segments under projection. Cornell University
Computer Science Technical Report TR 92-1292, July 1992.
Search Tools and Bibliographies
Academic Sites
Theory of Computing
Computational Biology
Computational Geometry
Internet Security
Miscellaneous
Jon M. Kleinberg
Department of Computer Science
Upson Hall
Cornell University
Ithaca, NY 14853
(607)255-4117
kleinber@cs.cornell.edu