Optimization with additional variables and constraints

✍ Scribed by Alpár Jüttner

• Book ID: 104076271
• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Weight: 181 KB
• Volume: 33
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2004.06.006

✦ Synopsis

Norton, Plotkin and Tardos proved that-loosely spoken, an LP problem is solvable in time O(T q k+1 ) if deleting k fixed columns or rows, we obtain a problem which can be solved by an algorithm that makes at most T steps and q comparisons. This paper improves this running time to O(T q k ).