WEIGHTED MULTIDIMENSIONAL SEARCH AND ITS APPLICATION TO CONVEX-OPTIMIZATION

Authors
AGARWALA R FERNANDEZBACA D
Citation
R. Agarwala et D. Fernandezbaca, WEIGHTED MULTIDIMENSIONAL SEARCH AND ITS APPLICATION TO CONVEX-OPTIMIZATION, SIAM journal on computing, 25(1), 1996, pp. 83-99
Citations number
35
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
25
Issue
1
Year of publication
1996
Pages
83 - 99
Database
ISI
SICI code
0097-5397(1996)25:1<83:WMSAIA>2.0.ZU;2-M
Abstract
We present a weighted version of Megiddo's multidimensional search tec hnique and use it to obtain faster algorithms for certain convex optim ization problems in R(d), for fixed d. This leads to speed-ups by a fa ctor of log(d) n for applications such as solving the Lagrangian duals of matroidal knapsack problems and of constrained optimum subgraph pr oblems on graphs of bounded tree-width.