Me interesarían mucho las referencias a la teoría de las funciones submodulares (desde lo básico hasta lo avanzado).
En particular, estoy estudiando aproximaciones a problemas de optimización difíciles y quiero desarrollar mis fundamentos en funciones submodulares, ya que son relevantes para los problemas de optimización que he estado estudiando.
Gracias por adelantado.
Respuestas:
Referencias como las sugeridas por Standa Zivny son, por supuesto, muy buenas. Permítanme agregar a la lista el nuevo libro de Andras Frank titulado "Conexiones en optimización combinatoria" publicado por Oxford University Press, 2011. Todas estas referencias tratan las funciones submodulares desde un punto de vista de optimización combinatoria clásica donde la submodularidad aparece principalmente en restricciones. Ha habido varias aplicaciones y desarrollos recientes con funciones objetivo submodulares para las cuales se necesita un punto de vista ligeramente diferente. Hay muchos documentos para dar una lista aquí. Sin embargo, recomendaría la encuesta de Shaddin Dughmi sobre extensiones continuas de funciones submodulares http://arxiv.org/abs/0912.0322v3 .
fuente
Las referencias que uso (y me gustan) son capítulos seleccionados en la Optimización combinatoria de 3 volúmenes de Schrijver: Poliedros y eficiencia (Springer) y Optimización combinatoria de Vygen (Springer). Hay un libro dedicado a las funciones submodulares de Fujishige: Submodular Functions and Optimization, volumen 58 de Annals of Discrete Mathematics, North-Holland (segunda edición de 2005).
fuente
Me gustaría agregar " Funciones submodulares y redes eléctricas " de H. Narayanan .
fuente
Uno de mis favoritos, la tesis de Jan vondrak y muchos de sus trabajos.
fuente
Dos publicaciones más 1. Goldengorin, B., Ghosh, D .: Un algoritmo de búsqueda multinivel para la maximización de funciones submodulares aplicadas al problema de partición de costo cuadrático. J. Glob. Optim. 32, 65-82 (2005)
fuente