A FULLY POLYNOMIAL EPSILON-APPROXIMATION CUTTING PLANE ALGORITHM FOR SOLVING COMBINATORIAL LINEAR-PROGRAMS CONTAINING A SUFFICIENTLY LARGE BALL

Authors
BOYD EA
Citation
Ea. Boyd, A FULLY POLYNOMIAL EPSILON-APPROXIMATION CUTTING PLANE ALGORITHM FOR SOLVING COMBINATORIAL LINEAR-PROGRAMS CONTAINING A SUFFICIENTLY LARGE BALL, Operations research letters, 20(2), 1997, pp. 59-63
Citations number
6
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
20
Issue
2
Year of publication
1997
Pages
59 - 63
Database
ISI
SICI code
0167-6377(1997)20:2<59:AFPECP>2.0.ZU;2-3
Abstract
A cutting plane algorithm is presented for finding E-approximate solut ions to integer programs contained in the unit hypercube and represent ed by a separation oracle. Under the assumption that a polynomially bo unded ball is contained in the feasible region of the problem, it is d emonstrated that the algorithm is an oracle fully polynomial epsilon a pproximation scheme. Implications of the result for 0/1 integer progra mming are discussed.