Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

2 votes
Accepted

Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?

Interior-point methods such as Khachiyan’s and Karmarkar’s are, indeed, polynomial in the size of the input, i.e., in the number of variables, constraints, and the bitlength of the coeficients. This ...
Emil Jeřábek's user avatar
0 votes

Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?

One possible way is to write a dummy objective function, such as $$maximize: \sum x_i$$ and let any good LP solver take care of the rest. The same is also suggested here.
codeR's user avatar
  • 1,022

Top 50 recent answers are included