Rounding of convex sets and efficient gradient methods for linear programming problems
DOI10.1080/10556780701550059zbMATH Open1192.90119OpenAlexW2111208481MaRDI QIDQ5459820FDOQ5459820
Authors:
Publication date: 29 April 2008
Published in: Optimization Methods \& Software (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/10556780701550059
Recommendations
- Linear Programming in O([n3/ln n]L) Operations
- A new polynomial-time algorithm for linear programming
- New algorithms for linear programming
- Rounding of Polytopes in the Real Number Model of Computation
- A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
convex optimizationnonlinear optimizationgradient methodsoptimal methodsrelative accuracycomplexity boundsfully polynomial approximation schemes
Convex programming (90C25) Linear programming (90C05) Large-scale problems in mathematical programming (90C06)
Cites Work
- Smooth minimization of non-smooth functions
- Introductory lectures on convex optimization. A basic course.
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Rounding of Polytopes in the Real Number Model of Computation
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Potential function methods for approximately solving linear programming problems: theory and practice.
- Minimum-volume enclosing ellipsoids and core sets
- Ellipsoidal approximations of convex sets based on the volumetric barrier
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
Cited In (6)
- Self-concordant barriers for convex approximations of structured convex sets
- OSGA: a fast subgradient algorithm with optimal complexity
- Barrier subgradient method
- The RPR2 rounding technique for semidefinite programs
- Gradient methods for minimizing composite functions
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
This page was built for publication: Rounding of convex sets and efficient gradient methods for linear programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459820)
