cours:c-2-24-1 [2018/11/12 13:27] angelopoulos [Internship] |
cours:c-2-24-1 [2019/11/06 16:17] (current) angelopoulos [Course lectures] |

| ==== Course lectures ==== | | ==== Course lectures ==== |

| | | |

- | [Sep **17**] **Linear **programming **(brief intro), **duality**, simplex **[DPV: 7:1**, 7:4**, 7:6]**, duality and optimality: **shortest path [WS: 7.3]. | + | [Sep **16**] **Quick introduction to linear **programming **and **duality [DPV: 7:1, 7:6]**. The primal-dual scheme. An application to the **shortest path **problem **[WS: 7.3]. |

| | | |

| + | [Sep 23] LP rounding for Vertex Cover. The Maximum Value problem. An 8-approximation using LP-rounding. Stochastic matchings. This follows Chapter 1 in [Mun2018] (see references). |

| | | |

| + | [Sep 30] A 3-approximation for the Maximum Value problem using Lagrangian relaxation. Prophet inequality. This follows chapters 2.1, 2.2 in [Mun2018]. |

| | | |

- | [**Sep 24**] **Simple rounding for vertex cover, integrality gap**, **duality and approximability **[**V: 12**], **primal-dual for vertex cover**, ** **a **sophisticated rounding for **the **generalized load balancing **problem **[KT: 11.7]**. | + | [**Oct 7**] **Submodular functions (sections 3.1**, **3.2 in **[**Mun2018**]**). Separation oracles and the ellipsoid method (briefly discussed**, **see**, **e.g., Section 4.3 in [WS 2011]). **a **quick introduction to online computation: **the **ski rental **problem. |

| | | |

| + | [Oct 14] How to design approximation schemes for scheduling [SW], a sophisticated rounding for the generalized load balancing problem [KT: 11.7], integrality gap, duality and approximability [V: 12]. |

| | | |

- | [Oct **1**] **The Maximum Value problem. An 8**-**approximation using LP-rounding. Stochastic matchings. This follows Chapter 1 in **[**Mun2018**] **(see references)**. | + | [Oct **21**] **Scheduling with precedence constraints, From offline to online [WS], Non**-**clairvoyant scheduling [MPT], Multiplicative Weights Update Method **[**AM**]. |

| | | |

- | [Oct **8**] **A 3-approximation for **the **Maximum Value problem using Lagrangian relaxation. Prophet inequality. This follows chapters 2.1**, **2.2 in **[**Mun2018**]. ** ** | + | [Oct **28**] **Application of **the **Multiplicative Weights Update Method for Solving Covering Linear Programs [OS]**, **Online Learning and the Metrical Task System **[**BB**]**, The Doubling Method**. |

| | | |

- | **[Oct 15] Submodular functions (sections 3.1**, **3.2 in [Mun2018]). Separation oracles **and the **ellipsoid method (briefly discussed, see, e**.**g**., **Section 4.3 in [WS 2011])**. | + | ****Final Exam:** Monday**, **November 25, time **and **place as for **the **lectures**. **This is a closed book exam**. **You are allowed a single A4 page of your notes**, ****one side only****. ** ** |

| + | **====Homeworks====** |

| | | |

- | **[Oct 22] Set cover via dual fitting (section 4.1. in [Mun 2018]). The ski rental problem (see Section 3 in [[https**:**//www.tau.ac.il/~nivb/download/pd**-**survey**.pdf|**this survey by Buchbinder and Naor]], also covered in Chapter 13 in [Mun2018]**). | + | **{{:cours**:**upload:HW1**-**2-24-1-2019**.pdf|**Homework 1}} (due on September 23**). |

| | | |

- | **[Oct 29] The Multiplicative Weight Update algorithm [AM] (see also in [[http**:**//www.satyenkale.com/papers/mw**-**survey**.pdf|**this survey by Arora et al.]]**)**. Application to the solution of covering linear programs [OS]**. | + | **{{**:**cours:upload:HW2**-**2-24-1-2019**.pdf|**Homework 2}} (due on September 30**). |

| | | |

- | **[Nov 5] Online learning and its relation with the Metrical Task System problem (based on [[http**:**//www.win.tue.nl/~nikhil/AU16/reading/blum**-**burch**-**learning**.pdf|**this paper by Blum and Burch]]**).** ** | + | **{{**:**cours:upload:HW3**-**2**-**24-1-2019**.pdf|**Homework 3}} (due on October 7**). |

- | **====Homeworks====** | + | |

| | | |

- | {{:cours:upload:2-24-1-**2018-homework1**.pdf|Homework **1**}} (due on October **8**). | + | {{:cours:upload:**HW4-**2-24-1-**2019**.pdf|Homework **4**}} (due on October **14**). |

| | | |

- | {{:cours:upload:2-24-1-**2018-homework2**.pdf|Homework **2**}} (due on October **15**). | + | {{:cours:upload:**HW6-**2-24-1-**2019**.pdf|Homework **5**}} (due on October **21**). |

| | | |

- | {{:cours:upload:2-24-1-**2018-homework3**.pdf|Homework **3**}} (due on **October 22**). | + | {{:cours:upload:**HW7-**2-24-1-**2019**.pdf|Homework **6**}} (due on **November 8**). |

| | | |

- | {{:cours:upload:2-24-1-2018-homework4.pdf|Homework 4}} (due on October 29). | |

| | | |

- | {{:cours:upload:homework-5_2-24-1_2018.pdf|Homework 5}} (due on November 5). | |

| | | |

- | {{:cours:upload:2-24-1_homework-6_2018.pdf|Homework 6}} (due on November 16). | |

| ==== Grading scheme, presentations, and homework policy==== | | ==== Grading scheme, presentations, and homework policy==== |

| | | |

- | There will be homeworks (**25**%), a class presentation (**25**%) and a final exam (50%). | + | There will be homeworks (**30**%), a class presentation (**20**%) and a final exam (50%). |

| | | |

- | **The presentations will be done during class **on November 12**. Please refer to the email for instructions. ** | + | Homework policy: you should not search for solutions on the internet. If, for some reason, you ended up using outside help, you must cite your sources. No collaboration among students is allowed. All homeworks will be due on the beginning of the class. We will not accept late homeworks, **except for serious reasons**. |

- | ** ** | + | |

- | Homework policy: you should not search for solutions on the internet. If, for some reason, you ended up using outside help, you must cite your sources. No collaboration among students is allowed. All homeworks will be due on the beginning of the class. We will not accept late homeworks**. ** | + | |

- | ** ** | + | |

- | **The **course exam** will be on **Monday**, **Nov 19**, in the same room as the lectures. The exam is closed-book, but you can bring a single A4-sized page with your notes. You can use only one side of the page**. ** ** | + | |

| | | |

| ==== Papers ==== | | ==== Papers ==== |

- | **The following is **a list of **suggested **papers for **class **presentation**: ** | + | **Here we will add **a list of papers for presentation. |

- | ** - [[http://math**.**mit.edu/~goemans/PAPERS/stoch_cover_latin.pdf|Stochastic covering and adaptivity ]] by Goemans and Vondrak. ** | + | |

- | ** - [[https://arxiv.org/pdf/1008.5356.pdf| When LP is the cure for your matching woes: improved bounds for stochastic matchings]] by Bansal et al. ** | + | |

- | ** - [[http://web.stanford.edu/%7Eashishg/papers/query-stoch.pdf|Asking the right questions: Model-driven optimization using probes]] by Goel et al. ** | + | |

- | ** - [[https://arxiv.org/pdf/0712.3936.pdf |Lagrangian relaxation and partial cover]] by Mestre. ** | + | |

- | ** - [[https://arxiv.org/pdf/1708.04903.pdf |Online primal-dual algorithms with configuration LPs]] by NK Thang. ** | + | |

- | ** - [[http://www.cs.cmu.edu/~anupamg/papers/stoch-online.pdf| Stochastic analysis for online combinatorial optimization problems]] by Garg et al. ** | + | |

- | ** - [[https://www.openu.ac.il/personal_sites/moran-feldman/publications/SICOMP2015.pdf| A tight linear (1/2)-approximation for unconstrained submodular maximization]] by Buchbinder et al. ** | + | |

- | ** - [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.7564&rep=rep1&type=pdf|LP rounding approximation algorithms for stochastic network design]] by Gupta et al. ** | + | |

- | ** - [[https://people.orie.cornell.edu/jmd388/publications/ConstrainedForrestJournal.pdf |A 3/2 approximation algorithm for some minimum-cost graph problems]] by Couetoux et al. ** | + | |

- | ** - [[https://papers.nips.cc/paper/6526-adaptive-maximization-of-pointwise-submodular-functions-with-budget-constraint.pdf|Adaptive maximization of pointwise submodular ** | + | |

- | **functions with budget constraint]] by Cuong and Xu. ** | + | |

- | ** ** | + | |

| | | |

| | | |

| + | * [[http://mattstreeter.org/Research/mstreeter_nips_2008.pdf|An online algorithm for maximizing submodular functions]] by Streeter and Golovin. |

| + | * [[https://web.stanford.edu/~ashishg/papers/query-stoch.pdf| Asking the right questions: Model-driven optimization using probes]] by Goel et al. |

| + | * [[http://www.jennwv.com/papers/taskassign.pdf|Online Task Assignment in Crowdsourcing Markets]] by Ho and Vaughan. |

| + | * [[http://people.iiis.tsinghua.edu.cn/~jianli/paper/sigmetric14.pdf|The Multi-shop Ski Rental Problem]] by Ai et al. |

| + | * [[https://papers.nips.cc/paper/4990-an-approximate-efficient-lp-solver-for-lp-rounding.pdf|An Approximate, Efficient Solver for LP Rounding]] by Sridhar et al. |

| + | * [[http://www.cs.uu.nl/research/techreps/repo/CS-1997/1997-39.pdf|Approximation algorithms for facility location problems]] by Shmoys et al. |

| + | * [[https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1786655/main.pdf|Online Linear Optimization for Job Scheduling Under Precedence Constraints]] by Takahiro et al. |

| + | * [[https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1786656/main.pdf|Combinatorial Online Predictionvia Metarounding]] by Takahiro et al. |

| + | * [[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/2005-Efficient_Algorithms_for_Online_Decision_Problems.pdf|Efficient algorithms for online decision problems]] by Kalai and Vempala. |

| + | |

| ==== Internship ==== | | ==== Internship ==== |

| | | |

| more broadly, to the research interests of the instructors. | | more broadly, to the research interests of the instructors. |

| | | |

- | Posted internships: | |

- | * {{:cours:upload:2-24-1-2018-stage-stochastic.pdf| Stochastic analysis of online algorithms for Steiner tree problems}} | |

| ==== References ==== | | ==== References ==== |

| | | |

| * [EK] D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, [[https://www.cs.cornell.edu/home/kleinber/networks-book/ | book]] | | * [EK] D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, [[https://www.cs.cornell.edu/home/kleinber/networks-book/ | book]] |

| * [AM] A. Madry, How to Get Rich (If You Have Good Advice) [[https://people.csail.mit.edu/madry/gems/notes/lecture1.pdf | notes ]] | | * [AM] A. Madry, How to Get Rich (If You Have Good Advice) [[https://people.csail.mit.edu/madry/gems/notes/lecture1.pdf | notes ]] |

- | * [DPV] S. Dasgupta, C.H. Papadimitriou, U. Vazirani, Algorithms, Mc Graw Hill, 2006 | + | * [DPV] S. Dasgupta, C.H. Papadimitriou, U. Vazirani, Algorithms, Mc Graw Hill, 2006 **[[http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf|Book]]** |

| * [DV] Ch. Dürr, J.-J. Vie, Programmation Efficace Les 128 Algorithmes Qu'Il Faut Avoir Compris et Codés en Python au Cours de sa Vie, Ellipses, 2016 | | * [DV] Ch. Dürr, J.-J. Vie, Programmation Efficace Les 128 Algorithmes Qu'Il Faut Avoir Compris et Codés en Python au Cours de sa Vie, Ellipses, 2016 |

| * [OS] O. Svensson, Multiplicative weight update method for covering LPs [[https://theory.epfl.ch/courses/topicstcs/Lecture112015.pdf | notes ]] | | * [OS] O. Svensson, Multiplicative weight update method for covering LPs [[https://theory.epfl.ch/courses/topicstcs/Lecture112015.pdf | notes ]] |

| + | * [MPT] R. Motwani, S. Phillips, E. Torng, Non-clairvoyant scheduling [[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=869EB6ECB1F7A2CBF7C0012A9DF43741?doi=10.1.1.38.1803&rep=rep1&type=pdf | paper]] |

| + | * [SW] P. Schuurman, G. Woeginger, Approximation schemes--A tutorial [[https://www.win.tue.nl/~gwoegi/papers/ptas.pdf | survey]] |

| + | * [BB] A. Blum and C. Burch, On-line Learning and the Metrical Task System Problem [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2057&rep=rep1&type=pdf|paper]] (you can also search for the journal version of this paper). |

| | | |