Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more
Kitahara and Mizuno get upper bounds for the maximum number of different basic feasible solutions generated by Dantzig�s simplex method. In this paper, we obtain lower bounds of the maximum number. Part of the results in this paper are shown in a paper by the authors as a quick report without proof. They present a … Read more
The problem of finding a minimum l^1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for l^1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an … Read more
We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are “easy”, that is, they are Lagrangian functions of explicitly known convex programs with “few” variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In … Read more
In this paper, we propose a simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming problem (LP). Our variant executes a natural finite termination procedure at each iteration and it is easy to implement the algorithm. Our algorithm admits an objective-function free polynomial-time complexity when it is applied to LPs whose dual feasible region … Read more
In their 1972 paper ‘How good is the simplex algorithm ?’ Klee and Minty present a class of problems the simplex algorithm for linear programming (LP) is not able to solve in a polynomial way. Later developments have resulted in algorithms by Khachiyan and Karmarkar that do solve LP in a polynomial way, although the … Read more
We consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the weighted analytic center of a polytope. We show that the problem has a dual of the same form and give complexity results for several different … Read more
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
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the dual simplex method with the most negative pivoting rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (2010) for the primal simplex method. We apply the result to the … Read more
We give an upper bound for the number of different basic feasible solutions generated by Dantzig’s simplex method (the simplex method with the most negative pivoting rule) for LP with bounded variables by extending the result of Kitahara and Mizuno (2010). We refine the analysis by them and improve an upper bound for a standard … Read more