Online Algorithms

* Online algorithms到底是啥？

  (取自http://www.cs.cmu.edu/afs/cs/academic/class/15750-s19/OldScribeNotes/lecture35.pdf开头)

**********************************↓2021春夏-本科毕业设计↓********************************

教学日历维护时间为2021年1月15日-2月28日

总References

一. Scheduling

 1. Online Virtual Machine Allocation with Predictions

二. Paging

1. Competitive caching with machine learned advice, Thodoris Lykouris, Sergei Vassilvitskii

First published in ICML 2018; last revised 21 Aug 2020 (this version, v4) 

三. Metric

1. Online Metric Algorithms with Untrusted Predictions (python代码) (两个例子，俩同学:程振威，田澳冉)

四. Ski rental

Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice （matlab代码）（一个同学：邢朗）

五. $k$-server

Learning-Augmented Online Algorithms for the 2-Server Problem on the Line and Generalizations (rust and python代码) （k-server on the line、2-taxi on the line，俩同学：欧阳嶂浩、冯明尧）

六. bin packing （施莹莹同学）

Simulation of Online Bin Packing in Practice 

Online algorithms for variants of bin packing

**********************************↑2021春夏-本科毕业设计↑********************************

    (取自https://www.cs.umd.edu/~samir/DCscheduling18/slides/Svitkina.pdf的第5页)

• https://github.com/thHube/Work-Function-Algorithm  (work function的实现)
• https://github.com/Lei-Xu/k-Server-Problem  (work function的实现)

https://www2.cs.duke.edu/courses/spring15/compsci590.1/

https://www.win.tue.nl/~nikhil/AU16/index.html

http://math.ucdenver.edu/~sborgwardt/wiki/index.php/Lagrangian_Duality

2021-01-18

• 对online algorithms感兴趣的人其实很多啊，在试图弄明白work function的时候，从这个slide发现了两个亮点：

一个亮点是“Online energy generation scheduling for microgrids with intermittent energy”这篇文章（work function相关，用到了look ahead，因此可以考虑with predictions。该文中的这段话很有启发性：Under typical settings, we show that CHASE achieves the best competitive ratio among all deterministic online algorithms, and the ratio is no larger than a small constant 3. We also extend our algorithms to intelligently leverage on limited prediction of the future, such as near-term demand or wind forecast ）。

另一个亮点是：

• “Online Algorithms - From Prediction to Decision-PhD thesis-Niangjun_Chen_2017”与“Data-driven Competitive Algorithms for Online Knapsack and Set Cover”这篇论文必须得看啊！

• Interestingly, a very similar metric space is powerful enough to model the noted “ski rental problem”, see Karlin, Manasse, Rudolph, and Sleator [68] for details. (摘自“Advanced Techniques for Dynamic Programming”)

2021-01-09

• online problem的Input包括两部分：以k-server problem为例，the first part of input = metric space + k；the online part of input = a sequence of requests。这是原来自己没有留心到的。

2021-01-08

• 以前看过的一个blog，也讲到了online algorithm，这个blog的意义还在于为本科生算法扩展内容提供素材。

2021-01-05

• 关于paging的randomized MARK算法competitive ratio分析，有图且好理解的是这儿的lecture 8。

2021-01-04

• 关于Adversary Models，讲得最简略而又最容易理解的是ebook-Randomized algorithms一书第13章的13.2节。从adversary的power来看：Oblivious < Adaptive online < Adaptive offline；从竞争比的大小来看：$c^{obl}<c^{aon}<c^{aof}<c^{det}$。
• 可以认为OPT算法由adversary设计，$\sigma$由adversary生成。上面$c^{det}$最大，是因为deterministic ALG太弱，弱在不是randomized。

2020-12-26

• 关于PDLA，首先得有Linear Programming Recap，这个所见最好的是Lecture 9 — September 30, 2014 Prof. Jelani Nelson。接下来的Lecture 10 — October 2, 2014 Prof. Jelani Nelson以Ski Rental为例讲了PD为工具的online algorithm，再结合ebook-The Design of Competitive Online Algorithms via a Primal-Dual Approach中的相应部分来看，比较好理解。
• ski rental：就ski rental的primal-dual approach来说，对于2-competitive的算法，有两种处理方式，一是increment $y$，这也最常见的方式，如lecture note1，lecture note2，lecture note3，分析都是用的approximate complementary slackness result；二是increment $x_{buy}$，这种方式的分析仍然是利用了approximate complementary slackness result，其提出好像是为了与基于primal dual的randomized online algorithm相对比。
• ski rental：基于primal dual的randomized online algorithm的分析较多，但是就其由来，即算法中的参数为何那么设定，讲这个的是lecture note3。但是最透彻的是Prof. Dr. Yann Disser所给的lecture notes的第7节部分。

2020-12-23

巴西的一位老师，随机部分较好。

2020-11-03

Online and other Myopic Algorithms (Fall 2019)

Algorithms and Uncertainty (Fall, 2016)

2020-11-01 

既然有The Design of Competitive Online Algorithms via a Primal–Dual Approach，那么是否可以考虑The Design of Competitive Online Algorithms via a Local Ratio Approach？

（On the Equivalence Between the Primal-Dual Schema and the Local Ratio Technique）

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2004/CS/CS-2004-01.pdf

（On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique）

https://epubs.siam.org/doi/pdf/10.1137/050625382

（Combinatorial Interpretations of Dual Fitting and Primal Fitting）

http://www.eng.biu.ac.il/~rawitzd/Papers/fitting.pdf

2020-10-28 

第一个看懂的list update的MTF分析：(https://www.cs.princeton.edu/courses/archive/spring13/cos521/notes/lecture5.pdf)

2020-7-31

Tim Roughgarden的lecture notes，真的应该好好通读! 比如，对于online paging的competitive ratio的证明，看得懂的就是从这位大师的17年的Beyond Worst-Case Analysis（lecture 3）开始的，再具体点，就是LRU的upper bound。看懂这个之后，再看“ebook-draft-Online Algorithms-Allan Borodin & Denis Pankratov-March 14, 2019-ch1-8”的第11页，就可以理解LRU与FIFO的相似性，从而理解“ebook-An Introduction to Online Computation Determinism, Randomization, Advice”所证明的FIFO的upper bound了。

• agnostic learing means: Make no assumptions about a specific functional relationship between $\mathbf{x}$ and $y$.  
  

2020-7-28

STOC‘20 Workshop on Algorithms with Predictions

Learning-Augmented Algorithms

Researchers

Dennis Komm (author of ebook-An Introduction to Online Computation Determinism, Randomization, Advice)

Teachers

Thomas Kesselheim (2017-2020的lecture notes都很好！)

Prof. Dr. Yann Disser

Online Algorithms

原文：https://www.cnblogs.com/liu-hong/p/13694625.html