Funções submodulares: solicitação de referência

11

Eu estaria muito interessado em referências à teoria das funções submodulares (do básico ao avançado).

Em particular, estou estudando aproximações para problemas de otimização rígida e quero desenvolver minhas bases em funções submodulares, pois são relevantes para os problemas de otimização que venho estudando.

Desde já, obrigado.

ds.algorithms reference-request approximation-algorithms optimization Nikhil
fonte
11
autopromoção desavergonhada: Algoritmo ganancioso de aproximação-Δ para cobertura de restrições arbitrárias e custo submodular .
Neal Young

Respostas:

8

Referências como as sugeridas por Standa Zivny são obviamente muito boas. Deixe-me adicionar à lista o novo livro de Andras Frank, intitulado "Connections in Combinatorial Optimization", publicado pela Oxford University Press, 2011. Todas essas referências tratam funções submodulares de um ponto de vista clássico de otimização combinatória, onde a submodularidade aparece principalmente em restrições. Houve várias aplicações e desenvolvimentos recentes com funções objetivas submodulares para as quais é necessário um ponto de vista ligeiramente diferente. Existem muitos documentos para dar uma lista aqui. No entanto, eu recomendaria a pesquisa de Shaddin Dughmi sobre extensões contínuas de funções submodulares http://arxiv.org/abs/0912.0322v3 .

Chandra Chekuri
fonte
Obrigado pela pesquisa, parece muito bom! Eu comprei recentemente o livro de Frank, mas ainda não consegui lê-lo, por isso fiquei um pouco relutante em recomendá-lo.
Standa Zivny
5
@Chandra, o tempo para que você escreva uma pesquisa sobre o material mais recente :)
Suresh Venkat
Obrigado pelo link da pesquisa. Eu estava procurando por algo semelhante a isso.
quer
9

As referências que eu uso (e similares) são capítulos selecionados na Otimização Combinatória de 3 volumes da Schrijver: Poliedros e Eficiência (Springer) e Otimização Combinatória da Vygen (Springer). Há um livro dedicado às funções submodulares de Fujishige: Submodular Functions and Optimization, volume 58 de Annals of Discrete Mathematics, Holanda do Norte (2ª edição de 2005).

Standa Zivny
fonte
2

Um dos meus favoritos, a tese de Jan vondrak e muitos de seus artigos.

Ashwinkumar BV
fonte
0

Mais duas publicações 1. Goldengorin, B., Ghosh, D .: Um algoritmo de busca multinível para a maximização de funções submodulares aplicadas ao problema da partição quadrática de custos. J. Glob. Optim. 32, 65-82 (2005)

  1. B. Goldengorin. Maximização de funções submodulares: algoritmos de teoria e enumeração. European Journal of Operational Research, 198 (1): 102–112, 2009
user56394
fonte