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.
Weighted Multidimensional Search and its
Application to Convex Optimization
Richa Agarwala and David Fernandez-Baca
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.
Contact site administrator at: email@example.com