Rounding of convex sets and efficient gradient methods for linear programming problems
(2004)
Files
dp2004_4.pdf
Open Access - Adobe PDF
- 215.7 KB
Details
- Authors
- Abstract
- 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 withrelative accuracy . We prove that the upper complexity bound for both ln schemes is O( n m ln n) iterations of a gradient-type method, where n and m, (n < m), are the sizes of the corresponding linear programming problems. The proposed schemes are based on preliminary computation of an ellipsoidal rounding for some polytopes in Rn . In both cases this computation can be performed very efficiently, in O(n2 m ln m) operations at most.
- Affiliations
Citations
Nesterov, Y. (2004). Rounding of convex sets and efficient gradient methods for linear programming problems (CORE Discussion Papers 2004/4). https://hdl.handle.net/2078.5/38372