Fonctions sous-modulaires: demande de référence

11

Je serais très intéressé par les références à la théorie des fonctions sous-modulaires (des bases aux avancées).

En particulier, j'étudie des approximations de problèmes d'optimisation difficiles et je souhaite développer mes fondations dans les fonctions sous-modulaires car elles sont pertinentes aux problèmes d'optimisation que j'ai étudiés.

Merci d'avance.

ds.algorithms reference-request approximation-algorithms optimization Nikhil
la source
1
autopromotion sans vergogne: Algorithme d'approximation Δ avide pour couvrir avec des contraintes arbitraires et des coûts sous-modulaires .
Neal Young

Réponses:

8

Des références comme celles suggérées par Standa Zivny sont bien sûr très bonnes. Permettez-moi d'ajouter à la liste le nouveau livre d'Andras Frank intitulé "Connections in Combinatorial Optimization" publié par Oxford University Press, 2011. Toutes ces références traitent les fonctions sous-modulaires d'un point de vue de l'optimisation combinatoire classique où la sous-modularité apparaît principalement dans les contraintes. Il y a eu plusieurs applications et développements récents avec des fonctions d'objectif sous-modulaires pour lesquels il faut un point de vue légèrement différent. Il existe de nombreux articles pour donner une liste ici. Je recommanderais cependant l'enquête de Shaddin Dughmi sur les extensions continues des fonctions sous-modulaires http://arxiv.org/abs/0912.0322v3 .

Chandra Chekuri
la source
Merci pour l'enquête, elle a l'air très bien! J'ai récemment acheté le livre de Frank, mais je n'ai pas encore réussi à le lire, donc j'étais un peu réticent à le recommander.
Standa Zivny
5
@Chandra, il est temps pour vous d'écrire une enquête sur les choses les plus récentes :)
Suresh Venkat
Merci pour le lien de l'enquête. Je cherchais quelque chose de similaire à cela.
Nikhil
9

Les références que j'utilise (et j'aime) sont des chapitres sélectionnés dans Schrijver's 3-volume Combinatorial Optimization: Polyhedra and Efficiency (Springer) et Vygen's Combinatorial Optimization (Springer). Il y a un livre consacré aux fonctions submodulaires par Fujishige: Fonctions et optimisation submodulaires, volume 58 des Annals of Discrete Mathematics, Hollande du Nord (2e édition de 2005).

Standa Zivny
la source
0

Deux autres publications 1. Goldengorin, B., Ghosh, D .: Un algorithme de recherche à plusieurs niveaux pour la maximisation des fonctions sous-modulaires appliquées au problème de partition des coûts quadratiques. J. Glob. Optim. 32, 65–82 (2005)

  1. B. Goldengorin. Maximisation des fonctions sous-modulaires: algorithmes de théorie et d'énumération. Journal européen de recherche opérationnelle, 198 (1): 102-112, 2009
user56394
la source