How Experts Can Solve LPs Online
How Experts Can Solve LPs Online
复制标题
专家如何在线解决有限合伙人问题
DOI：
10.1007/978-3-662-44777-2_43
复制
发表时间：
2014
影响因子：
4.8
通讯作者：
M. Molinaro
中科院分区：
文献类型：
--
作者：
Anupam Gupta;M. Molinaro
考虑了约束矩阵的列按随机顺序排列时，线性规划问题的在线求解问题。这个问题受到了很多关注：主要的开放性问题是要弄清楚LP的右侧必须有多大（与约束左侧的条目相比）才能在线获得（1 + e）-近似？已知RHS必须是Ω（e − 2 logm）乘以左侧，其中m是约束的数量。
We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention: the main open question is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraint) to get (1 + e)-approximations online? It is known that the RHS has to be Ω(e − 2 logm) times the left-hand sides, where m is the number of constraints.