<p>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 <a href="http://arxiv.org/abs/0912.0322v3">http://arxiv.org/abs/0912.0322v3</a>.</p>

CC BY-SA 3.0
2011-08-11T19:00:41.600Z
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.
Standa Zivny
CC BY-SA 3.0
2011-08-11T22:20:51.957Z
@Chandra, time for you to write a survey on the most recent stuff :)
Suresh Venkat
CC BY-SA 3.0
2011-08-12T01:32:10.473Z
Thanks for the survey link. I was looking for something similar to this.
Nikhil
CC BY-SA 3.0
2011-08-11T16:50:47.720Z
2011-08-11T16:55:50.803Z
2011-08-11T16:55:50.803Z
Chandra Chekuri
<p>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).</p>

CC BY-SA 3.0
2011-08-10T17:24:14.450Z
2011-08-10T17:24:14.450Z
Standa Zivny
<p>I would like to add "<a href="http://www.ee.iitb.ac.in/~hn/book/SubmodularFunction_2ed.pdf" rel="nofollow">Submodular Functions and Electrical Networks</a>" by <a href="http://www.ee.iitb.ac.in/~hn/" rel="nofollow">H. Narayanan</a>. </p>

CC BY-SA 3.0
2013-04-26T15:47:22.690Z
Thanks. Corrected. There are notes on matroids as well on his homepage.
bkc4
CC BY-SA 3.0
2013-04-23T18:49:02.330Z
2013-04-26T15:46:22.890Z
2013-04-26T15:46:22.890Z
bkc4
<p>One of my favorites, <a href="http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf" rel="nofollow">Jan vondrak's thesis</a> and many of his papers. </p>

CC BY-SA 3.0
2013-04-24T22:21:54.043Z
2013-04-24T22:21:54.043Z
Ashwinkumar B V
<p>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)</p>

<ol start="2">
<li>B. Goldengorin. Maximization of submodular functions: Theory and enumeration algorithms. European Journal of Operational Research, 198(1):102–112, 2009</li>
</ol>

CC BY-SA 4.0
2020-03-24T12:03:56.273Z
2020-03-24T12:03:56.273Z
user56394
<p>I would be very much interested in references to the theory of submodular functions (from basics to advanced).</p>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2012-11-04T16:56:26.517Z
shameless self-promotion: [Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost](http://www.cs.ucr.edu/~neal/publications?paper=Koufogiannakis12Greedy).
Neal Young
<ds.algorithms><reference-request><approximation-algorithms><optimization>
Submodular functions: reference request
Nikhil
# Submodular functions: reference request

(Asked by: username_0 on 2011-08-10)

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.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, optimization

> **Comments:**
> **username_1**: shameless self-promotion: [Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost](http://www.cs.ucr.edu/~neal/publications?paper=Koufogiannakis12Greedy).  

---

## 5 answers

### Answer by username_2 on 2011-08-11. Score: 8 | Accepted answer

References such as the ones suggested by username_3 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>.

> **Comments:**
> **username_3**: 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.  
> **username_4**: @Chandra, time for you to write a survey on the most recent stuff :)  
> **username_0**: Thanks for the survey link. I was looking for something similar to this.  

---

### Answer by username_3 on 2011-08-10. Score: 9

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


---

### Answer by username_5 on 2013-04-23. Score: 4

I would like to add "[Submodular Functions and Electrical Networks](http://www.ee.iitb.ac.in/~hn/book/SubmodularFunction_2ed.pdf)" by [H. Narayanan](http://www.ee.iitb.ac.in/~hn/).

> **Comments:**
> **username_5**: Thanks. Corrected. There are notes on matroids as well on his homepage.  

---

### Answer by username_6 on 2013-04-24. Score: 3

One of my favorites, [Jan vondrak's thesis](http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf) and many of his papers.


---

### Answer by username_7 on 2020-03-24. Score: 0

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)

2. B. Goldengorin. Maximization of submodular functions: Theory and enumeration algorithms. European Journal of Operational Research, 198(1):102–112, 2009


---

