Buyback problem with discrete concave valuation functions |
| |
Institution: | 1. Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan;2. Department of Industrial Engineering and Economics, Tokyo Institute of Technology, Tokyo 152-8550, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Buyback problem Discrete concave function Gross substitutes valuation Online discrete optimization problem Matroid |
本文献已被 ScienceDirect 等数据库收录! |
|