An efficient, strongly polynomial, ε-approximation parametric optimization scheme

✍ Scribed by S.N. Kabadi; Y.P. Aneja

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 379 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00142-7

✦ Synopsis

Given a set X 5 Z", vectors c, d E IK", an interval [a, b] C R, a fixed 0 < E < 1, and an oracle that, for any 0 < E < 1 finds an E-approximate solution to problem max{hTx 1 x E X} for any h E RU", we present a theoretically and practically efficient e-approximation algorithm, for the problem min{u( A) 1 A E [a, b]}, where u(A) = max{(c -Ad)Tx ) x E X}. When the elements of the set X are {0,&l} vectors, the total number of iterations required by our algorithm is O(~~'(logn)~). @ 1997 Elsevier Science B.V.