TR-2001-17

Optimization with additional variables and constraints

Alpár Jüttner

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



Abstract

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:

@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}
}


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