Funciones submodulares: solicitud de referencia

11

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.

Nikhil
fuente

Respuestas:

8

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 .

Chandra Chekuri
fuente
Gracias por la encuesta, se ve muy bien! Recientemente compré el libro de Frank, pero aún no he podido leerlo, así que me resistí un poco a recomendarlo.
Standa Zivny
55
@Chandra, es hora de que escribas una encuesta sobre las cosas más recientes :)
Suresh Venkat
Gracias por el enlace de la encuesta. Estaba buscando algo similar a esto.
Nikhil
9

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).

Standa Zivny
fuente
0

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)

  1. B. Goldengorin. Maximización de funciones submodulares: algoritmos de teoría y enumeración. European Journal of Operational Research, 198 (1): 102–112, 2009
usuario56394
fuente