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(Tqk+1) to O(Tqk), 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:

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

Last modification: 13.3.2018. Please email your comments to Tamás Király!