Online contention resolution schemes (OCRSs) are effective rounding techniques for online combinatorial optimization problems with stochastic inputs. These schemes randomly and sequentially round a fractional solution to a relaxed problem that can be formulated in advance. In this study, we propose OCRSs for online stochastic knapsack problems and, more generally, online stochastic generalized assignment problems. In our setup, each item arriving sequentially is inserted into one of multiple knapsacks or discarded. Its size, which follows a known distribution, is revealed only after insertion. The goal of the problem is to maximize the acceptance probability, which is the smallest probability among the items being placed in the knapsack. Since the item sizes are unknown beforehand, a violation of capacity constraints may occur. Thus, we consider two distinct settings: the hard constraint setting, where items that cause such violations are rejected, and the soft constraint setting, where these items are accepted. Under the hard constraint setting, we present an algorithm with an acceptance probability of 1/3 and show that no algorithm can achieve an acceptance probability greater than 3/7. Under the soft constraint setting, we propose an algorithm with an acceptance probability of 1/2 and demonstrate that this is best possible.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Online Contention Resolution Schemes for Size-Stochastic Knapsacks

  • Toru Yoshinaga,
  • Yasushi Kawase

摘要

Online contention resolution schemes (OCRSs) are effective rounding techniques for online combinatorial optimization problems with stochastic inputs. These schemes randomly and sequentially round a fractional solution to a relaxed problem that can be formulated in advance. In this study, we propose OCRSs for online stochastic knapsack problems and, more generally, online stochastic generalized assignment problems. In our setup, each item arriving sequentially is inserted into one of multiple knapsacks or discarded. Its size, which follows a known distribution, is revealed only after insertion. The goal of the problem is to maximize the acceptance probability, which is the smallest probability among the items being placed in the knapsack. Since the item sizes are unknown beforehand, a violation of capacity constraints may occur. Thus, we consider two distinct settings: the hard constraint setting, where items that cause such violations are rejected, and the soft constraint setting, where these items are accepted. Under the hard constraint setting, we present an algorithm with an acceptance probability of 1/3 and show that no algorithm can achieve an acceptance probability greater than 3/7. Under the soft constraint setting, we propose an algorithm with an acceptance probability of 1/2 and demonstrate that this is best possible.