Optimal pricing of capacitated networks

Grigoriev, Alexander and Loon van, Joyce and Sitters, René and Uetz, Marc (2009) Optimal pricing of capacitated networks. Networks, 53 (1). pp. 79-87. ISSN 0028-3045

PDF
Restricted to UT campus only: Request a copy
1213b

Abstract:	We address the algorithmic complexity of a profit maximization problem in capacitated, undirected networks. We are asked to price a set of $m$ capacitated network links to serve a set of $n$ potential customers. Each customer is interested in purchasing a network connection that is specified by a simple path in the network and has a maximum budget that we assume to be known to the seller. The goal is to decide which customers to serve, and to determine prices for all network links in order to maximize the total profit. We address this pricing problem in different network topologies. More specifically, we derive several results on the algorithmic complexity of this profit maximization problem, given that the network is either a path, a cycle, a tree, or a grid. Our results include approximation algorithms as well as inapproximability results.
Item Type:	Article
Copyright:	© 2009 Wiley InterScience
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62734
Official URL:	http://dx.doi.org/10.1002/net.20260
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 263742