In the space we will post a detailed list of the topics covered with
pointers to the relevant literature.
| Date |
Topic |
Reference |
Lecturer |
Handouts |
| Oct 22 |
Introduction and basic concepts |
[Lov83] |
Khaled |
|
| Oct 29 |
SMF minimization: Lovaz's extension |
[Lov83] |
Khaled |
Ellipsoid method |
| Nov 5 |
SMF minimization: Schrijver's algorithm, part I |
[Sch00] [McC06] |
Khaled |
|
| Nov 12 |
SMF minimization: Schrijver's algorithm, part II |
[Sch00] [McC06] |
Khaled |
|
| Nov 19 |
Submodular set cover |
[Fu00] |
Julian |
|
| Nov 26 |
Class cancelled (AG1 event) |
|
|
|
| Dec 3 |
Generalized Steiner networks |
[Ja00] |
Julian |
|
| Dec 10 |
Influence in social networks |
[MR06] |
Julian |
|
| Dec 17 |
SMF maximization: Greedy and random sampling |
[NWF 77]
[FMV 07]
|
Rajiv |
|
| Jan 14 |
SMF maximization: Local search |
[FMV 07]
|
Rajiv |
|
| Jan 21 |
SMF maximization: Lower bounds |
[FMV 07]
|
Rajiv |
|
