Mishra, S. ; Radhakrishnan, Jaikumar ; Sivasubramanian, S.
(2002)
*On the hardness of approximating minimum monopoly problems*
Lecture Notes in Computer Science, 2556
.
pp. 277-288.
ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/index/NHV8W9ME3HP20R97...

Related URL: http://dx.doi.org/10.1007/3-540-36206-1_25

## Abstract

We consider inapproximability for two graph optimisation problems called monopoly and partial monopoly. We prove that these problems cannot be approximated within a factor of (⅓-∈) ln n and ( ½-∈) ln n, unless NP Dtime(n^{O(log log n)}), respectively. We also show that, if Δ is the maximum degree in a graph G, then both problems cannot be approximated within a factor of ln Δ-O(ln ln Δ), unless P = NP, though both these problems can be approximated within a factor of ln(Δ) + O(1). Finally, for cubic graphs, we give a 1.6154 approximation algorithm for the monopoly problem and a 5/3 approximation algorithm for partial monopoly problem, and show that they are APX-complete.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer. |

ID Code: | 89511 |

Deposited On: | 27 Apr 2012 13:38 |

Last Modified: | 27 Apr 2012 13:38 |

Repository Staff Only: item control page