Philip N. Klein

Científico informático estadounidense

Philip N. Klein es un informático estadounidense y profesor de la Universidad de Brown . Su investigación se centra en algoritmos para problemas de optimización en grafos.  

Klein es miembro de la Association for Computing Machinery ^[1] y recibió el Premio Presidencial al Joven Investigador de la National Science Foundation (1991). ^[2] Recibió el Premio Philip J. Bray a la Excelencia en la Enseñanza de las Ciencias de la Universidad Brown (2007) y fue miembro del Instituto Radcliffe de Estudios Avanzados de la Universidad de Harvard (2015-16). ^[2] Se graduó summa cum laude de Harvard con una licenciatura en Matemáticas Aplicadas y obtuvo un doctorado en Ciencias de la Computación en el MIT . ^[3]

Contribuciones clave

• En 1991, Klein y sus entonces estudiantes Ajit Agrawal y R. Ravi presentaron un algoritmo de aproximación para el diseño de redes que se considera "el primer uso altamente sofisticado del método primal-dual en el diseño de algoritmos de aproximación". ^[4] En 2023, esta investigación recibió el premio Test of Time de 30 años del Simposio Anual de la ACM sobre Teoría de la Computación (STOC). ^{[5] [6] [7] [4]}
• En 1994, Klein y Robert E. Tarjan dieron un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos, basado en una técnica de muestreo de David Karger. ^{[8] [9] [10]}
• En 2005, Klein presentó un algoritmo de tiempo lineal para encontrar un recorrido casi óptimo de un viajante de comercio en un gráfico plano. ^{[11] [12]}

Libros

Klein ha publicado dos libros de texto:

• Klein, Philip N. (2014). Introducción a la criptografía: secretos y promesas. Nueva York, NY, EE. UU. ISBN 978-1-107-01788-7.OCLC 863632974  .{{cite book}}: CS1 maint: location missing publisher (link)^[13]
• Klein, Philip N. (2013). Codificación de la matriz: álgebra lineal a través de aplicaciones a la informática. [Newton, Mass.]: Newtonian Press. ISBN 978-0-615-85673-5.OCLC 855087626  .^[14]

Referencias

1. "Philip N Klein". awards.acm.org . Consultado el 29 de mayo de 2022 .
2. "Philip N. Klein". cs.brown.edu . Archivado desde el original el 3 de enero de 2022 . Consultado el 27 de junio de 2022 .
3. "Philip N. Klein". Instituto Radcliffe de Estudios Avanzados de la Universidad de Harvard . Archivado desde el original el 19 de abril de 2022. Consultado el 27 de junio de 2022 .
4. Hochbaum, Dorit. Algoritmos de aproximación para problemas NP-difíciles . pag. 158.
5. "Philip Klein y exalumnos de Brown CS reciben el premio STOC Test Of Time 2023".
6. Agrawal, Ajit; Klein, Philip; Ravi, R. (1995). "Cuando los árboles colisionan: Un algoritmo de aproximación para el problema generalizado de Steiner en redes". Revista SIAM de Computación . 24 (3): 440–456. doi :10.1137/S0097539792236237.
7. Agrawal, Ajit; Klein, Felipe; Ravi, R. (1991). ""Cuando los árboles chocan: Un algoritmo de aproximación para el problema generalizado de Steiner en redes"". Actas del 23º Simposio Anual ACM sobre Teoría de la Computación : 134–144.
8. Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Cambridge University Press. pp. Sección 10.3.
9. Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "Un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos". Revista de la ACM . 42 (2): 321–328. doi : 10.1145/201019.201022 . S2CID  832583.
10. Klein, Philip N.; Tarjan, Robert E. (1994). "Un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos". Actas del vigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '94 . págs. 9-15. doi :10.1145/195058.195084. ISBN 0897916638. Número de identificación del sujeto  15667728.
11. Klein, Philip N. (2008). "Un esquema de aproximación de tiempo lineal para TSP en grafos planos no dirigidos con pesos de arista". Revista SIAM de Computación . 37 (6): 1926–1952. CiteSeerX 10.1.1.155.897 . doi :10.1137/060649562. 
12. Klein, Philip N. (2005). "Un esquema de aproximación de tiempo lineal para TSP ponderado planar". 46.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'05) . pp. 647–656. doi :10.1109/SFCS.2005.7. ISBN 0-7695-2468-0. Número de identificación del sujeto  16327107.
13. Klein, Philip N. (2014). Introducción a la criptografía: secretos y promesas. Nueva York, NY, EE. UU. ISBN 978-1-107-01788-7.OCLC 863632974  .{{cite book}}: CS1 maint: location missing publisher (link)
14. Klein, Philip N. (2013). Codificación de la matriz: álgebra lineal a través de aplicaciones a la informática. [Newton, Mass.]: Newtonian Press. ISBN 978-0-615-85673-5.OCLC 855087626  .