TY - GEN
T1 - How to sell a graph
T2 - 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006
AU - Grigoriev, Alexander
AU - Van Loon, Joyce
AU - Sitters, René
AU - Uetz, Marc
PY - 2006
Y1 - 2006
N2 - 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-ε.
AB - 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-ε.
KW - Computational complexity
KW - Dynamic programming
KW - Fully polynomial time approximation scheme
KW - Highway problem
KW - Pricing problems
KW - Tollbooth problem
UR - http://www.scopus.com/inward/record.url?scp=33845519057&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33845519057&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33845519057
SN - 3540483810
SN - 9783540483816
VL - 4271 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 125
EP - 136
BT - Graph-Theoretic Concepts in Computer Science - 32nd International Workshop, WG 2006, Revised Papers
PB - Springer/Verlag
Y2 - 22 June 2006 through 24 June 2006
ER -
