9
$\begingroup$

I would be very much interested in references to the theory of submodular functions (from basics to advanced).

In particular, I am studying approximations to hard optimization problems and I want to develop my foundations in submodular functions as they are relevant to the optimization problems I have been studying.

Thanks in advance.

$\endgroup$
8
$\begingroup$

References such as the ones suggested by Standa Zivny are of course very good. Let me add to the list the new book by Andras Frank titled "Connections in Combinatorial Optimization" published by Oxford University Press, 2011. All of these references treat submodular functions from a classical combinatorial optimization point of view where submodularity primarily appears in constraints. There have been several recent applications and developments with submodular objective functions for which one needs a slightly different view point. There are many papers to give a list here. I would however recommend Shaddin Dughmi's survey on continuous extensions of submodular functions http://arxiv.org/abs/0912.0322v3.

$\endgroup$
  • $\begingroup$ Thank you for the survey, it looks very good! I've recently purchased Frank's book, but haven't managet to read it yet so I was a bit reluctant to recommend it. $\endgroup$ – Standa Zivny Aug 11 '11 at 19:00
  • 3
    $\begingroup$ @Chandra, time for you to write a survey on the most recent stuff :) $\endgroup$ – Suresh Venkat Aug 11 '11 at 22:20
  • $\begingroup$ Thanks for the survey link. I was looking for something similar to this. $\endgroup$ – Nikhil Aug 12 '11 at 1:32
8
$\begingroup$

The references I use (and like) are selected chapters in Schrijver's 3-volume Combinatorial Optimization: Polyhedra and Efficiency (Springer) and Vygen's Combinatorial Optimization (Springer). There is a book devoted to submodular functions by Fujishige: Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics, North-Holland (2nd edition from 2005).

$\endgroup$
4
$\begingroup$

I would like to add "Submodular Functions and Electrical Networks" by H. Narayanan.

$\endgroup$
  • $\begingroup$ Thanks. Corrected. There are notes on matroids as well on his homepage. $\endgroup$ – Sagar Kale Apr 26 '13 at 15:47
2
$\begingroup$

One of my favorites, Jan vondrak's thesis and many of his papers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.