How to sell a graph: guidelines for graph retailers


Grigoriev, Alexander and Loon, Joyce van 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 (pp. pp. 125-136).

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page