Weighted Multidimensional Search and its Application to Convex Optimization
|
Home About Browse Search Register Subscriptions Deposit Papers Help |
Agarwala, Richa and Fernandez-Baca, David (1992) Weighted Multidimensional Search and its Application to Convex Optimization. Technical Report TR92-34, Department of Computer Science, Iowa State University.
| Full text available as: | Postscript Adobe PDF |
Abstract
Weighted Multidimensional Search and its Application to Convex Optimization by Richa Agarwala and David Fernandez-Baca TR 92-34 Abstract We present a weighted version of Megiddo's multidimensional search technique and use it to obtain faster algorithms for certain convex optimization problems in R^d, for fixed d. This leads to speed-ups by a factor of log^d n for applications such as solving the Lagrangian duals of matroidal knapsack problems and of constrained optimum subgraph problems on graphs of bounded tree-width.
| Subjects: | All uncategorized technical reports |
| ID code: | 00000037 |
| Deposited by: | Staff Account on 05 November 1992 |
Contact site administrator at: ssg@cs.iastate.edu