Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems Export

@article{citeulike:4613250, abstract = {We demonstrate the impossibility of strongly polynomial algorithms for the allocation problem, in the comparison model and in the algebraic tree computation model, that follow from lower bound results. Consequently, there are no strongly polynomial algorithms for nonlinear (concave) separable optimization over a totally unimodular constraint matrix. This is in contrast to the case when the objective is linear. We present scaling-based algorithms that use a greedy algorithm as a subroutine. The algorithms are polynomial for the allocation problem and its extensions and are also optimal for the simple allocation problem and the generalized upper bounds allocation problem, in that the complexity meets the lower bound derived from the comparison model. For other extensions of the allocation problem the scaling-based algorithms presented here are the fastest known. These algorithms are also polynomial time algorithms for solving with ε accuracy the allocation problem and its extension in continuous variables.}, author = {Hochbaum, Dorit S.}, citeulike-article-id = {4613250}, citeulike-linkout-0 = {http://dx.doi.org/10.2307/3690226}, citeulike-linkout-1 = {http://www.jstor.org/stable/3690226}, doi = {10.2307/3690226}, issn = {0364765X}, journal = {Mathematics of Operations Research}, keywords = {article, masters, optimization, resourceallocation}, number = {2}, pages = {390--409}, posted-at = {2009-05-23 21:26:36}, priority = {2}, publisher = {INFORMS}, title = {Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems}, url = {http://dx.doi.org/10.2307/3690226}, volume = {19}, year = {1994} }

TY - JOUR ID - citeulike:4613250 L3 - citeulike-article-id:4613250 N2 - We demonstrate the impossibility of strongly polynomial algorithms for the allocation problem, in the comparison model and in the algebraic tree computation model, that follow from lower bound results. Consequently, there are no strongly polynomial algorithms for nonlinear (concave) separable optimization over a totally unimodular constraint matrix. This is in contrast to the case when the objective is linear. We present scaling-based algorithms that use a greedy algorithm as a subroutine. The algorithms are polynomial for the allocation problem and its extensions and are also optimal for the simple allocation problem and the generalized upper bounds allocation problem, in that the complexity meets the lower bound derived from the comparison model. For other extensions of the allocation problem the scaling-based algorithms presented here are the fastest known. These algorithms are also polynomial time algorithms for solving with ε accuracy the allocation problem and its extension in continuous variables. IS - 2 JF - Mathematics of Operations Research SN - 0364765X EP - 409 TI - Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems PB - INFORMS VL - 19 SP - 390 KW - article KW - masters KW - optimization KW - resourceallocation AU - Hochbaum, Dorit PY - 1994/// UR - http://dx.doi.org/10.2307/3690226 ER -