Recently I have come across a paper which talks of (1+)-inapproximability and of logarithmic approximation.While I have a basic knowledge of computational complexity (I more or less know what it means to be in P, NP, NP-hard and so on), I tried to study some basic texts on approximability but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean?If you want to know the paper I was referring to, it was DasGupta & Desai. On the complexity of Newmans community finding approach for biological and social networks. Journal of Computer and System Sciences 79, n. 1 (2013): 5067. The found inapproximability is a property of the modularity measure (the so-called Q) related to the Newman-Girvan algorithm for finding community structure in networks, a measure whose maximization has been proved NP-complete by Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, and Wagner in 2008. Thank you in advance.
What is inapproximability of NP-hard problems?
np hard;approximation