  


A polynomial algorithm for linear feasibility problems given by separation oracles
Sergei Chubanov (sergei.chubanovunisiegen.de) Abstract: The algorithm proposed in this paper runs in a polynomial oracle time, i.e., in a number of arithmetic operations and calls to the separation oracle bounded by a polynomial in the number of variables and in the maximum binary size of an entry of the coefficient matrix. This algorithm is much simpler than traditional polynomial algorithms such as the ellipsoid method and the volumetric barrier method. In particular, we do not need the notion of volume to prove the polynomial complexity of our algorithm. Keywords: linear programming, convex optimization Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 01/27/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  