  We study an assortment optimization problem under a multi-purchase choice
model in which customers choose a bundle of up to one product from each of two
product categories. Different bundles have different utilities and the bundle
price is the summation of the prices of products in it. For the uncapacitated
setting where any set of products can be offered, we prove that this problem is
strongly NP-hard. We show that an adjusted-revenue-ordered assortment provides
a 1/2-approximation. Furthermore, we develop an approximation framework based
on a linear programming relaxation of the problem and obtain a
0.74-approximation algorithm. This approximation ratio almost matches the
integrality gap of the linear program, which is proven to be at most 0.75. For
the capacitated setting, we prove that there does not exist a constant-factor
approximation algorithm assuming the Exponential Time Hypothesis. The same
hardness result holds for settings with general bundle prices or more than two
categories. Finally, we conduct numerical experiments on randomly generated
problem instances. The average approximation ratios of our algorithms are over
99%.
