Approximation algorithms for the partial assignment problem

Abstract

In the partial assignment problem, a seller has an item set M = {i(1), i(2), ..., i(m)}, the amount of each item is exactly one. There are n buyers N = {b(1), b(2), ..., b(n)}, each buyer b y has a preferred bundle B-p subset of M and a value function f(p)(.). Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b(p) can have some positive value if the seller assigns a subset of b(p)'s preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f(p) (S-p) for buyer b(p) and S-p subset of B-p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max Sigma(n)(p=1) f(p)(S-p). We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1/root m-approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of (1 -1/e). (C) 2020 Elsevier B.V. All rights reserved.