TR-2001-17

Optimization with additional variables and constraints

Alpár Jüttner

Published in:
Operations Research Letters. 33 (2005) 301-311.

Norton, Plotkin and Tardos [12] proved that - loosely spoken, a linear programming problem can be solved in strongly polynomial time if, by deleting a constant number k of columns, it can be converted to a problem which is already known to be solvable in strongly polynomial time. In this paper, by a more careful application of Megiddo's technique, the running time of this algorithm is reduced from O(Tq^k+1) to O(Tq^k), where T is the running time of the basic algorithm, and q is the number of the comparisons made by it. For small k it can cause significant improvement on the algorithms using method of [12]. This approach also improves the consequences of the result of [12].

Bibtex entry:

@techreport{egres-01-17,

AUTHOR	=	{Jüttner, Alp{\'a}r},
TITLE	=	{Optimization with additional variables and constraints},
NOTE	=	{{\tt www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2001},
NUMBER	=	{TR-2001-17}

}