archives

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