  


A strongly polynomial algorithm for linear optimization problems having 01 optimal solutions
Sergei Chubanov (sergei.chubanovunisiegen.de) Abstract: We present a strongly polynomial algorithm for linear optimization problems of the form min{cxAx = b, x >= 0} having 01 vectors among their optimal solutions. The algorithm runs in time O(n^4*max\{m,log n}), where n is the number of variables and m is the number of equations. The algorithm also constructs necessary and sufficient optimality conditions for 01 solutions in the form of a linear system. Keywords: Linear programming, strongly polynomial algorithm Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 01/06/2014 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  