Back to Search
Start Over
A polynomial oracle-time algorithm for convex integer minimization.
- Source :
-
Mathematical Programming . Jan2011, Vol. 126 Issue 1, p97-117. 21p. 1 Diagram. - Publication Year :
- 2011
-
Abstract
- In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 126
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 56796435
- Full Text :
- https://doi.org/10.1007/s10107-009-0276-7