How to sell a graph: guidelines for graph retailers


Share/Save/Bookmark

Grigoriev, Alexander and Loon van, Joyce and Sitters, René and Uetz, Marc (2006) How to sell a graph: guidelines for graph retailers. In: 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, 22-24 June 2006, Bergen, Norway.

[img]PDF
Restricted to UT campus only
: Request a copy
235Kb
Abstract: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-\varepsilon}$.
Item Type:Conference or Workshop Item
Copyright:© 2006 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62211
Official URL:http://dx.doi.org/10.1007/11917496_12
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page