12
$\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.

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2011 at 19:00
  • 5
    $\begingroup$ @Chandra, time for you to write a survey on the most recent stuff :) $\endgroup$
    – Suresh Venkat
    Aug 11, 2011 at 22:20
  • $\begingroup$ Thanks for the survey link. I was looking for something similar to this. $\endgroup$
    – Nikhil
    Aug 12, 2011 at 1:32
9
$\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).

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Corrected. There are notes on matroids as well on his homepage. $\endgroup$
    – Black Sea
    Apr 26, 2013 at 15:47
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

Two more publications 1. Goldengorin, B., Ghosh, D.: A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Glob. Optim. 32, 65–82 (2005)

  1. B. Goldengorin. Maximization of submodular functions: Theory and enumeration algorithms. European Journal of Operational Research, 198(1):102–112, 2009
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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