Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs

Details Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs

2012-03-08

arxiv.org/abs/1203.1940v1

Computer Science

Computer Science and Game Theory

Scientific paper

Consider the following problem. A seller has infinite copies of n products represented by nodes in a graph. There are m consumers, each has a budget and wants to buy two products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit. This problem is called the Graph Vertex Pricing (GVP) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and k-partite graphs. We show that there exists an FPTAS for GVP on graphs with bounded treewidth. This result is also extended to an FPTAS for the more general Single-Minded Pricing problem. On bounded genus graphs we present a PTAS and show that GVP is NP-hard even on planar graphs. We study the integrality gap of the Sherali-Adams relaxation of the natural LP which has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying constant number of rounds of Sherali-Adams relaxation makes the integrality gap of the natural LP arbitrarily close to one. On k-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three.

Affiliated with

Also associated with

No associations

Rating

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-301057