Weighted Multidimensional Search and Its Application to Convex Optimization
Richa Agarwala, David Fernández‐Baca · SIAM Journal on Computing · 1996
We present a weighted version of Megiddo’s multidimensional search technique and use it to obtain faster algorithms for certain convex optimization problems in ${\bf 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.