Paper Info
Title
Weighted Multidimensional Search And Its Application To Convex Optimization
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.
Year
DOI
Venue
1996
10.1137/S0097539792241928
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
computational geometry, convex optimization, Lagrangian relaxation, multidimensional search
Journal
25
Issue
ISSN
Citations 
1
0097-5397
5
PageRank 
References 
Authors
0.42
11
2
Name
Order
Citations
PageRank
Richa Agarwala131058.02
David Fernández-Baca220123.65