# 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).

PDF
Restricted to UT campus only : Request a copy 240kB |

Abstract: | We consider a profit maximization problem where we are asked to price a set of items that are to be assigned to a set of customers. The items can be represented as the edges of an undirected (multi)graph , 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 , and we assume that each bundle forms a simple path in . 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 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 . |

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: | https://doi.org/10.1007/11917496_12 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page