Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142208 | Operations Research Letters | 2016 | 5 Pages |
Abstract
We consider the problem of solving multiple “coupled” root-finding problems at once, in that we can evaluate every function at the same point simultaneously. Using a dynamic programming formulation, we show that a sequential bisection algorithm is a close-to-optimal method for finding a ranking with respect to the zeros of these functions. We show the ranking can be found in linear time, prove an asymptotic approximation guarantee of 1.44, and conjecture that this policy is near-optimal.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stephen N. Pallone, Peter I. Frazier, Shane G. Henderson,