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 p has a preferred bundle B p ⊆ 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 ⊆ 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 ⁡ ∑ p = 1 n 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 / 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 ) .