###
Speaker:
Euiwoong Lee

###
Title:
Hardness of Graph Pricing through Generalized Max-Dicut

###
Abstract:

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.