|
|||||
|
|
Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization |
|
| Authors: | Vaibhav Srivastava Francesco Bullo |
| Institution: | 1. Mechanical and Aerospace Engineering Department, Princeton University, Princeton, NJ 08544, USA;2. Center for Control, Dynamical Systems, and Computation, University of California, Santa Barbara, CA 93106, USA |
| Abstract: | We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities. |
| Keywords: | Sigmoid utility/S-curve Knapsack problem Generalized assignment problem Bin-packing problem Multi-choice knapsack problem Human attention allocation |
| 本文献已被 ScienceDirect 等数据库收录！ | |