How to Sell a Graph: Guidelines for Graph Retailers

We consider a profit maximization problem where we are asked to price a set of

m

items that are to be assigned to a set of

n

customers. The items can be represented as the edges of an undirected (multi)graph

G

, where an edge multiplicity larger than one corresponds to multiple copies of the same item. Each customer is interested in purchasing a bundle of edges of

G

, and we assume that each bundle forms a simple path in

G

. Each customer has a known budget for her respective bundle, and is interested only in that particular bundle. The goal is to determine item prices and a feasible assignment of items to customers in order to maximize the total profit. When the underlying graph

G

is a path, we derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and edge multiplicities are one, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the underlying graph is a grid, and edge multiplicities are one, we show that it is even NP-complete to approximate the maximum profit to within a factor

n

1 − − ε

.