Speaker: Euiwoong Lee

Title: 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.