Rounding of convex sets and efficient gradient methods for linear programming problems

摘要

In this paper, we propose new efficient gradient schemes for two non-trivial classes of linear programming problems. These schemes are designed to compute approximate solutions with relative accuracy . We prove that the upper complexity bound for both schemes is O(((n ln m)/)ln n) iterations of a gradient-type method, where n and m (n