📄 http:^^www.cs.cornell.edu^info^people^kleinber^kleinber.html

📁 This data set contains WWW-pages collected from computer science departments of various universities
💻 HTML
字号:
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

<html><head><TITLE>Jon Kleinberg's Homepage</TITLE></head><body><h1> Jon Kleinberg </h1><i><dl><dt> <!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><a href="mailto:kleinber@cs.cornell.edu">kleinber@cs.cornell.edu</a><dt> Assistant Professor of <!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.cornell.edu">Computer Science</a><dt> <!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><a href="http://www.cornell.edu">Cornell University</a><dt> Ithaca, NY  14853-7501</dl></i>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<P><LI> approximation algorithms for routing anddisjoint paths problems in networks;<LI> adversarial queueing theory, an approach to analyzing the stabilityof network routing protocols without probabilistic assumptions;<LI> geometric methods in combinatorial optimization, particularlythe use of positive semi-definite programming; and<LI> geometric algorithms for studying molecular conformation.<P>I am spending the 1996-97 academic year visiting the <!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><A HREF="http://www.almaden.ibm.com/almaden/">IBM Almaden Research Center.</A><P>Click here to see<UL><LI><b><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><A HREF="#papers">Selected Publications</A></b><LI><b><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><A HREF="#links">Miscellaneous Links</A></b></UL><P><H2><A NAME = "papers">PAPERS</a></H2><H3>Approximation Algorithms and Combinatorial Optimization</H3><LI> J. Kleinberg.  <!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-uf.ps">Single-source unsplittable flow.</A>Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,to appear.<P><LI> J. Kleinberg, R. Rubinfeld.  <!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-exp.ps">Short paths in expander graphs.</A>Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,to appear.<P><LI> J. Kleinberg, E. Tardos.  <!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs95.ps">Disjointpaths in densely embedded graphs.</A>Proc. 36th IEEE Symposium on Foundations of Computer Science,1995.  <P><LI> J. Kleinberg, E. Tardos.  <!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/stoc95.ps">Approximations for the disjoint paths problem in high-diameter planar networks.</A>Proc. 27th ACM Symposium on Theory of Computing, 1995.<P><LI> A. Aggarwal, J. Kleinberg, D. Williamson.  <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/stoc96-node.ps">Node-disjointpaths on the mesh, and a new trade-off in VLSI layout.</A>Proc. 28th ACM Symposium on Theory of Computing, 1995.<P><LI> M. Goemans, J. Kleinberg.  <!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda96-latency.ps">An improvedapproximation ratio for the minimum latency problem.</A>Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.<P><LI> J. Kleinberg, M. Goemans.  <!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/theta.ps">The Lovasz thetafunction and a semi-definite programming relaxation of vertex cover.</A>To appear in SIAM J. Discrete Math.<P><H3>On-Line Algorithms</H3><LI> J. Kleinberg.  <!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs94.ps">The localization problem formobile robots.</A>  Proc. 35th IEEE Symposium on Foundations of ComputerScience, 1994.<P><LI> J. Kleinberg.  <!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda94-search.ps">On-line search in a simplepolygon.</A>  Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.<P><LI> J. Kleinberg.  <!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ipl-bal.ps">A lower bound for two-serverbalancing algorithms.</A>  Information Processing Letters 51(1994).<P><LI> R. El-Yaniv, J. Kleinberg.  <!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ipl-plane.ps">Geometric two-serveralgorithms.</A>  Information Processing Letters 53(1995).<P><LI> J. Kleinberg.  <!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ms.ps">On-line algorithms for robotnavigation and server problems.</A>  MIT/LCS/TR-641.  (Master's Thesis.)<P><H3>Parallel and Distributed Computing</H3><LI> D.M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, F.T. Leighton, Z. Liu.<!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-aqt.ps">Universal stability results for greedy contention-resolution protocols.</A>Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,to appear.<P><LI> A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson.Adversarial queueing theory.Proc. 28th ACM Symposium on Theory of Computing, 1995.<P><LI> J. Kleinberg, H. Attiya, N. Lynch.  <!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/istcs95.ps">Trade-offsbetween message delivery and quiesce times in connection managementprotocols.</A>  Proc. 3rd Israel Symposium on Theory of Computing and Systems,1995.<P><LI> J. Kleinberg, S. Mullainathan.  <!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/podc93.ps">Resource boundsand combinations of consensus objects.</A>  Proc. 12th ACM Symposium onPrinciples of Distributed Computing, 1993.<P><H3>Geometric Algorithms</H3><LI> B. Berger, J. Kleinberg, F.T. Leighton.  Reconstructing aThree-Dimensional Model with Arbitrary Errors.Proc. 28th ACM Symposium on Theory of Computing, 1995.<P><LI> D. Huttenlocher, J. Kleinberg.  <!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda94-proj.ps">Comparing point sets under projection.</A>  Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.<P><LI> D. Huttenlocher, K. Kedem, J. Kleinberg.  <!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/geom92.ps">On dynamic Voronoi diagrams and the minimum Hausdorff distance for pointsets under Euclidean motion in the plane.</A>  Proc. 8th ACM Symposiumon Computational Geometry, 1992.<P><LI> D. Huttenlocher, J. Kleinberg,  <!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/iv.ps">Invariantsof set of points or line segments under projection.</A>  Cornell UniversityComputer Science Technical Report TR 92-1292, July 1992.<P><H2><A NAME = "links">SOME LINKS</a></H2><H3>Search Tools and Bibliographies</H3><UL><li><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><A HREF="http://altavista.digital.com/">AltaVista.</A><li><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><A HREF="http://guide.infoseek.com/Home?page=Home.html&sv=N2">Infoseek.</A><li><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><A HREF="http://www.excite.com/">Excite.</A><li><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><A HREF="http://www.yahoo.com/">Yahoo.</A><li><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><A HREF="http://s18.bigyellow.com/">NYNEX Yellow Pages.</A><li><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><A HREF="http://glimpse.cs.arizona.edu:1994/bib/">Glimpse computer science bibliographies.</A><li><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><A HREF="http://cs-tr.cs.cornell.edu/">NCSTRL: Networked Computer Science Technical Reports Library.</A> <li><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><A HREF="http://theory.lcs.mit.edu/~dmjones/hbp/">David Jones's Hypertext Bibliography Project.</A></UL><H3>Academic Sites</H3><UL><li><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><A HREF="http://www.cornell.edu/">Cornell University.</A><li><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><A HREF="http://www.cs.cornell.edu">Cornell Computer Science.</A><li><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><A HREF="http://www.orie.cornell.edu">Cornell Operations Research.</A><li><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><A HREF="http://www.lcs.mit.edu">MIT Lab for Computer Science.</A><li><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><A HREF="http://theory.lcs.mit.edu">MIT LCS Theory of Computation Group.</A><li><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><A HREF="http://www-cs.stanford.edu">Stanford Computer Science.</A><li><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><A HREF="http://www.cs.berkeley.edu">Berkeley Computer Science.</A><li><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><A HREF="http://cra.org/">Computing Research Association.</A><li><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><A HREF="http://www.nsf.gov/">National Science Foundation.</A></UL><H3>Theory of Computing</H3><UL><li><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><A HREF="http://sigact.acm.org/tcs-rolodex/">TCS Virtual Address Book.</A><li><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><A HREF="http://liinwww.ira.uka.de/bibliography/Theory/index.html">Bibliographies on Theory/Foundations of Computer Science.</A><li><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><A HREF="http://www.nada.kth.se/~viggo/problemlist/compendium.html">Crescenzi/Kann Compendium of NP Optimization Problems.</A><li><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><A HREF="http://www.umiacs.umd.edu:80/events/FOCS96/">1996 FOCS conference.</A><li><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><A HREF="http://www.siam.org/meetings/da97/da97home.htm">1997 SODA conference.</A><li><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><A HREF="http://hercule.csci.unt.edu:80/stoc97/">1997 STOC conference.</A></UL><H3>Computational Biology</H3><UL><li><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><A HREF="http://www-hto.usc.edu/index.html">Computational Biology at USC.</A><li><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><A HREF="http://iris4.carb.nist.gov/">CARB Biocomputing Resources.</A><li><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><A HREF="http://gn.sdsc.edu:70/1/CCMS/Servers">SDSC's List of Computational Biology Servers.</A></UL><H3>Computational Geometry</H3><UL><li><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><A HREF="http://www.ics.uci.edu/~eppstein/junkyard/">David Eppstein's Geometry Junkyard.</A><li><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><A HREF="http://www.cs.duke.edu/~jeffe/compgeom/">Jeff Erickson's Computational Geometry Page.</A></UL><H3>Internet Security</H3><UL><li><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><A HREF="http://www.mitre.org/resources/centers/infosec/public-security-index.html">MITRE Corp.'s Security Information Resources.</A><li><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><A HREF="http://www.cs.princeton.edu/sip/">Princeton Safe Internet Programming Group.</A><li><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><A HREF="http://theory.lcs.mit.edu/~rivest/crypto-security.html">Ron Rivest's Cryptography and Security Links.</A></UL><H3>Miscellaneous</H3><UL><li><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><A HREF="http://home.netscape.com/">Netscape.</A><li><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><A HREF="http://www.intellicast.com/weather/usa">Intellicast.</A><li><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><A HREF="http://www.cnn.com/">CNN Interactive.</A><li><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><A HREF="http://www.usta.com/">U.S. Tennis Association.</A><li><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><A HREF="http://www.uschess.org/">U.S. Chess Online.</A><li><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><A HREF="http://www.cartalk.com/">Car Talk.</A></UL><ADDRESS>Jon M. Kleinberg</ADDRESS><ADDRESS>Department of Computer Science</ADDRESS><ADDRESS>Upson Hall</ADDRESS><ADDRESS>Cornell University</ADDRESS><ADDRESS>Ithaca, NY 14853</ADDRESS><ADDRESS>(607)255-4117</ADDRESS><ADDRESS>kleinber@cs.cornell.edu</ADDRESS>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -