New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Divide and conquer: A polynomial algorithm for linear programming

SpeakerSergei Chubanov

We present a polynomial algorithm for solving systems of linear inequalities. The algorithm uses a divide-and-conquer procedure based on projections onto half-spaces generated by valid inequalities which are obtained in the course of the procedure. If used appropriately, the procedure either finds a feasible solution or proves that one of the inequalities in the system holds as an equation for every integer feasible solution. This fact is used to develop a polynomial algorithm which either finds a feasible solution or decides that the system is infeasible. The algorithm can find a feasible solution or decide that there are no 0,1-solutions in strongly polynomial time.