How to sell a graph: guidelines for graph retailers

Alexander Grigoriev, Joyce van Loon, René Sitters, Marc Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)

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 − − ε.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers
EditorsFedor V. Fomin
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages125-136
Number of pages12
ISBN (Electronic)978-3-540-48382-3
ISBN (Print)978-3-540-48381-6
DOIs
Publication statusPublished - Oct 2006
Event32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006 - Bergen, Norway
Duration: 22 Jun 200624 Jun 2006
Conference number: 32

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume4271
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006
Abbreviated titleWG
CountryNorway
CityBergen
Period22/06/0624/06/06

Keywords

  • Pricing problems
  • Tollbooth problem
  • Highway problem
  • Computational complexity
  • Dynamic programming
  • Fully polynomial time approximation scheme

Fingerprint Dive into the research topics of 'How to sell a graph: guidelines for graph retailers'. Together they form a unique fingerprint.

Cite this