Approximability of identifying codes and locating–dominating codes

We study the approximability and inapproximability of finding identifying codes and locating–dominating codes of the minimum size. In general graphs, we show that it is possible to approximate both problems within a logarithmic factor, but sublogarithmic approximation ratios are intractable. In bounded-degree graphs, there is a trivial constant-factor approximation algorithm, but arbitrarily low approximation ratios remain intractable. In so-called local graphs, there is a polynomial-time approximation scheme. We also consider fractional packing of codes and a related problem of finding minimum-weight codes.