𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the continuous unbounded knapsack problem with uncertain coefficients

✍ Scribed by Eduardo Conde

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
166 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of O(n log(n)) time for this optimization problem.

πŸ“œ SIMILAR VOLUMES

On the complexity of some geometric prob
On the complexity of some geometric problems in unbounded dimension
✍ Nimrod Megiddo πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 429 KB

This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit ball% and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven no

On the solution of forward–backward SDEs
On the solution of forward–backward SDEs with monotone and continuous coefficients
✍ Ying Hu πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 98 KB

in the forward equation (see also [13] for the existence of solution to one-dimensional FBSDEs with bounded Lipschitz coe cients and non-degenerate di usion in the forward equation). In [14], Hu and Peng introduced the monotonicity condition, under which the FBSDEs can be solved, and their main idea