Buyback problem with discrete concave valuation functions
Buyback problem with discrete concave valuation functions
复制标题
DOI：
10.1016/j.disopt.2017.07.002
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
Shun Fukuda;A. Shioura;T. Tokuyama
中科院分区：
文献类型：
--
作者：
Shun Fukuda;A. Shioura;T. Tokuyama
We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.
