---
title: "Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem"
authors:
  - "Long Tran-Thanh"
  - "Yingce Xia"
  - "Tao Qin"
  - "Nicholas R. Jennings"
doi: ""
url: "https://ijcai.org/proceedings/2015/63"
pdf: "https://ijcai.org/proceedings/2015/0063.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "403-409"
track: "Main Track"
keywords:
---

# Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem

Long Tran-Thanh, Yingce Xia, Tao Qin, Nicholas R. Jennings

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 403-409.

## Abstract

We study the stochastic multiple-choice knapsack problem, where a set of Kitems, whose value and weight are random variables, arrive to the system at each time step, and a decision maker has to choose at most one item to put into the knapsack without exceeding its capacity. The goal is the decision-maker is to maximise the total expected value of chosen items with respect to the knapsack capacity and a finite time horizon.We provide the first comprehensive theoretical analysis of the problem. In particular, we propose OPT-S-MCKP, the first algorithm that achieves optimality when the value-weight distributions are known. This algorithm also enjoys O(√{T}) performance loss, where T is the finite time horizon, in the unknown value-weight distributions scenario.We also further develop two novel approximation methods, FR-S-MCKP and G-S-MCKP, and we prove that FR-S-MCKP achieves O(√{T}) performance loss in both known and unknown value-weight distributions cases, while enjoying polynomial computational complexity per time step. On the other hand, G-S-MCKP does not have theoretical guarantees, but it still provides good performance in practice with linear running time.