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

    PAPERS

    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.

    SOME LINKS

    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