David Bernard Shmoys (nacido en 1959) es profesor en la Escuela de Investigación de Operaciones e Ingeniería de la Información y en el Departamento de Ciencias de la Computación de la Universidad de Cornell . Obtuvo su Ph.D. de la Universidad de California, Berkeley en 1984. Su enfoque principal ha sido el diseño y análisis de algoritmos para problemas de optimización discretos.
David Shmoys | |
---|---|
Nació | 1959 (61 a 62 años de edad) |
alma mater | Princeton , Universidad de California, Berkeley |
Premios | Premio Frederick W. Lanchester (2013) |
Carrera científica | |
Campos | Ciencias de la Computación , Teoría de la complejidad computacional |
Instituciones | Cornell |
Tesis | Algoritmos de aproximación para problemas de secuenciación, programación y diseño de redes de comunicación (1984) |
Asesor de doctorado | Eugene Lawler |
Sitio web | gente |
En particular, su trabajo ha destacado el papel de la programación lineal en el diseño de algoritmos de aproximación para problemas NP-hard . Es conocido por su investigación pionera en proporcionar la primera garantía de desempeño de factor constante para varios problemas de programación y agrupamiento, incluidos los problemas de k-center y k-median y el problema de asignación generalizada. Los esquemas de aproximación de tiempo polinómico que desarrolló para problemas de programación han encontrado aplicaciones en muchos trabajos posteriores. Su investigación actual incluye optimización estocástica , sostenibilidad computacional y técnicas de optimización en biología computacional. Shmoys está casado con Éva Tardos , quien es profesora de Ciencias de la Computación Jacob Gould Schurman en la Universidad de Cornell.
Contribuciones clave
Dos de sus contribuciones clave son
- Algoritmo de aproximación de factor constante para el problema de asignación generalizado y la programación de máquinas paralelas no relacionadas .
- Algoritmo de aproximación de factor constante para k-medianas y problema de ubicación de instalaciones .
Estas contribuciones se describen brevemente a continuación:
El artículo [1] es un trabajo conjunto de David Shmoys y Eva Tardos.
El problema de asignación generalizada puede verse como el siguiente problema de programar una máquina paralela no relacionada con los costos. Cada uno de trabajos independientes (denotados ) tienen que ser procesados exactamente por uno de máquinas paralelas no relacionadas (indicadas ). No relacionado implica que el mismo trabajo puede requerir una cantidad diferente de tiempo de procesamiento en diferentes máquinas. Trabajo acepta unidades de tiempo cuando se procesa por máquina e incurre en un costo . Dado y , deseamos decidir si existe un horario con el costo total como máximo tal que para cada máquina su carga, el tiempo total de procesamiento requerido para los trabajos asignados es como máximo . Al escalar los tiempos de procesamiento, podemos suponer, sin pérdida de generalidad, que los límites de carga de la máquina satisfacen. `` En otras palabras, el problema de asignación generalizado es encontrar un programa de costo mínimo sujeto a la restricción de que la capacidad de producción, que la carga máxima de la máquina es como máximo ".
El trabajo de Shmoys con Lenstra y Tardos citado aquí [2] da un algoritmo de aproximación 2 para el caso del costo unitario. El algoritmo se basa en un diseño inteligente de programa lineal utilizando poda paramétrica y luego redondeando una solución de punto extremo del programa lineal de forma determinista. El algoritmo para el problema de asignación generalizada se basa en un LP similar mediante poda paramétrica y luego usando una nueva técnica de redondeo en un gráfico bipartito cuidadosamente diseñado. Enunciamos ahora la formulación LP y describimos brevemente la técnica de redondeo.
Adivinamos el valor óptimo de makespan y escribe el siguiente LP. Esta técnica se conoce como poda paramétrica.
;
- ;
- ;
- ;
- ;
La solución LP obtenida se redondea luego a una solución integral de la siguiente manera. Un gráfico bipartito ponderadoesta construido. Un lado del gráfico bipartito contiene los nodos de trabajo,, y el otro lado contiene varias copias de cada nodo de máquina, , dónde . Para construir los bordes a los nodos de la máquina correspondientes a, por ejemplo, máquina, los primeros trabajos se organizan en orden decreciente de tiempo de procesamiento . Por simplicidad, supongamos,. Ahora encuentra el índice mínimo, tal que . Incluido en todos los bordes con distinto de cero y establezca sus pesos en . Crea el borde y establezca su peso en . Esto asegura que el peso total de los bordes incidentes en el vértice es como máximo 1. Si , luego crea un borde con peso . Continúe con la asignación de bordes a En una forma similar.
En el gráfico bipartito así creado, cada nodo de trabajo en tiene un peso de borde total de 1 incidente en él, y cada nodo de máquina en tiene bordes con un peso total como máximo 1 incidente sobre él. Por lo tanto, el vector es una instancia de coincidencia fraccional en y así se puede redondear para obtener una correspondencia integral del mismo costo.
Ahora, considerando el orden de los tiempos de procesamiento de los trabajos en los nodos de las máquinas durante la construcción de y usando un argumento de carga fácil, se puede probar el siguiente teorema:
Teorema: Si tiene una solución factible, entonces se puede construir un cronograma con makespan y costo .
Desde , se obtiene una aproximación de 2.
Medianas K y problema de ubicación de instalaciones
El artículo [3] es un trabajo conjunto de Moses Charikar , Sudipto Guha , Éva Tardos y David Shmoys. Obtienen unaproximación al problema métrico k medianas . Este fue el primer documento en romper el más conocido anteriormente aproximación.
Shmoys también ha trabajado mucho en el problema de la ubicación de las instalaciones . Sus resultados recientes incluyen la obtención de unalgoritmo de aproximación para el problema de ubicación de instalaciones capacitadas. El trabajo conjunto con Fabian Chudak , [4] ha dado como resultado la mejora de la anterior conocidaaproximación para el mismo problema. Su algoritmo se basa en una variante de redondeo aleatorio llamado redondeo aleatorio con respaldo, ya que se incorpora una solución de respaldo para corregir el hecho de que el redondeo aleatorio ordinario rara vez genera una solución factible al problema de cobertura del conjunto asociado .
Para la versión no capacitada del problema de ubicación de las instalaciones, nuevamente en un trabajo conjunto con Chudak [5] obtuvo una-Algoritmo de aproximación que supuso una mejora significativa sobre las garantías de aproximación conocidas anteriormente. El algoritmo mejorado funciona redondeando una solución fraccionaria óptima de una relajación de programación lineal y utilizando las propiedades de las soluciones óptimas del programa lineal y una generalización de una técnica de descomposición.
Premios y honores
David Shmoys es miembro de ACM y miembro del Instituto de Investigación de Operaciones y Ciencias de la Gestión (INFORMS) (2013). Recibió el Premio a la Excelencia en la Enseñanza Sonny Yau de la Facultad de Ingeniería tres veces y ha sido galardonado con el Premio al Joven Investigador Presidencial NSF y el Premio Frederick W. Lanchester (2013)
Referencias
- ^ Shmoys, DB ; Tardos, É. (1993). "Un algoritmo de aproximación para el problema de asignación generalizada". Programación matemática . 62 (1–3): 461–474. doi : 10.1007 / BF01585178 . S2CID 9027754 .
- ^ Lenstra, JK; Shmoys, DB ; Tardos, É. (1990). "Algoritmos de aproximación para la programación de máquinas paralelas no relacionadas" . Programación matemática . 46 (1-3): 259-271. doi : 10.1007 / BF01585745 . S2CID 206799898 .
- ^ Charikar, M .; Guha, S .; Tardos, É .; Shmoys, DB (2002). "Un algoritmo de aproximación de factores constantes para el problema k-Mediana" . Revista de Ciencias de la Computación y Sistemas . 65 : 129-149. doi : 10.1006 / jcss.2002.1882 .
- ^ Chudak, FNA; Williamson, DP (2004). "Algoritmos de aproximación mejorados para problemas de ubicación de instalaciones capacitadas". Programación matemática . 102 (2): 207. CiteSeerX 10.1.1.53.5219 . doi : 10.1007 / s10107-004-0524-9 . S2CID 40133143 .
- ^ Chudak, FNA; Shmoys, DB (2003). "Algoritmos de aproximación mejorados para el problema de ubicación de instalaciones no capacitadas". Revista SIAM de Computación . 33 : 1–25. doi : 10.1137 / S0097539703405754 .
enlaces externos
- Página de inicio de David Shmoys
- Página de inicio de Éva Tardos