Joint Placement and Routing of Network Function Chains in Data Centers
论文中涉及两个算法：random roudning[offline] && multiplicative weight updating[online]
- 相同点
模型相同 - 不同点
| offline | 请求rate预先已知 | random rounding | ||
| online | opposite | MWU |
- random rounding
看了半天啊，后来发现就是把random rounding算法中的cheroff-bound重新推了一下。唯一不同的是假定了OPT = Ω(N). N为number of constraints. 因为模型
image.png
目标值受约束限制
通过假定，可以得出通过random rouding后得到的目标值与constraint呈线性关系。
