Template-type: ReDif-Paper 1.0
Author-Name: Grigoriev Alexander 
Author-Name: Loon, Joyce van
Author-Name: Sitters, René 
Author-Name: Uetz, Marc 
Author-workplace-name: METEOR
Title: How to Sell a Graph: Guidelines for Graph Retailers
Abstract: We consider a profit maximization problem when pricing a set of m items which can be represented as the edges of an undirected multi graph G. There is a set of n customers, each of which is interested in purchasing a bundle of edges of G, and we assume that these edges form a simple path in G. Each customer has a known budget for her respective bundle. Customers are single minded, so they are only interested in that particular bundle. The objective is to find a pricing and a feasible assignment of items to customers in order to maximize the total profit. We discuss the complexity of the problem when the underlying graph is a path, and derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and all items are unique, 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 items are unique, we show that it is even NP-complete to approximate the problem to within a factor n1-2.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2006
Number: 001
File-URL: http://arnop.unimaas.nl/show.cgi?fid=3980
File-Format: application/pdf
File-Size: 244496
Handle: RePEc:unm:umamet:2006001