NP-Hardness and Approximation Algorithms for Iterative Pricing on Social Networks with Externalities.
Chenli ShenWensong LinPublished in: Int. J. Found. Comput. Sci. (2021)
Keyphrases
- np hardness
- approximation algorithms
- social networks
- np hard
- special case
- vertex cover
- worst case
- set cover
- randomized algorithms
- constant factor
- linear programming
- open shop
- primal dual
- network effects
- approximation ratio
- graphical models
- lower bound
- search algorithm
- constant factor approximation
- combinatorial auctions
- network structure
- upper bound