## A polynomial algorithm for linear feasibility problems given by separation oracles

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 … Read more

## A generalized simplex method for integer problems given by verification oracles

We consider a linear problem over a finite set of integer vectors and assume that there is a verification oracle, which is an algorithm being able to verify whether a given vector optimizes a given linear function over the feasible set. Given an initial solution, the algorithm proposed in this paper finds an optimal solution … Read more

## A polynomial-time descent method for separable convex optimization problems with linear constraints

We propose a polynomial algorithm for a separable convex optimization problem with linear constraints. We do not make any additional assumptions about the structure of the objective function except for polynomial computability. That is, the objective function can be non-differentiable. The running time of our algorithm is polynomial in the the size of the input … Read more

## A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of … Read more

## A strongly polynomial algorithm for linear optimization problems having 0-1 optimal solutions

We present a strongly polynomial algorithm for linear optimization problems of the form min{cx|Ax = b, x >= 0} having 0-1 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 … Read more

## A polynomial projection algorithm for linear programming

We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either fi nds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the … Read more

## A polynomial relaxation-type algorithm for linear programming

The paper proposes a polynomial algorithm for solving systems of linear inequalities. The algorithm uses a polynomial relaxation-type procedure which either finds a solution for Ax = b, 0