Microsoft Word - review_response_OLP_2.docx

We thank the reviewer s for the careful feedback and appreciate the time spent reading our paper. Detailed responses are as below: Literature on online L P (OLP) and the contribution of our work: (i) From the algorithmic perspective, our algorithm has a strongly polynomial O(nnz(A)) flop complexity (linear in the number of non - zero entries in A), while the previous OLP algorithms all require solving O(log n) or O(n) of LP s ( increasing to the full size over time) . For example, Agrawal e t al. (2014) solved O(log n) LPs and Kesselheim et a l . As far as we know, the algorithm is the first of its kind and the most efficient OLP algorithm so far. As mentioned by the reviewer, our algorithms share similarity with the network control algorithm in Neely, M.J. (2010), but our analysis extends their analysis (in i.i.