Hardness of Graph Pricing through Generalized Max-Dicut
The Graph Pricing problem is among the fundamental problems whose approximability is not well-understood. While there is a simple combinatorial
¼-approximation algorithm, the best hardness result remains at
½ assuming the Unique Games Conjecture (UGC). We show that it is NP-hard to approximate within a factor better than
¼ under the UGC, so that the simple combinatorial algorithm might be the best possible.
This work is based on the effort to view the Graph Pricing problem as a Constraint Satisfaction Problem (CSP) simpler than the standard and complicated formulation. We propose the problem called Generalized Max-Dicut(T), which has a domain size T + 1 for every T ≥ 1 . Generalized Max-Dicut(1) is well-known Max-Dicut. Besides its connection to Graph Pricing, the hardness of Generalized Max-Dicut is interesting in its own right since in most arity two CSPs studied in the literature, SDP-based algorithms perform better than LP-based or combinatorial algorithms --- for this arity two CSP, a simple combinatorial algorithm does the best.