  We consider an optimization problem posed by an actual newspaper company,
which consists of computing a minimum length route for a delivery truck, such
that the driver only stops at street crossings, each time delivering copies to
all customers adjacent to the crossing. This can be modeled as an abstract
problem that takes an unweighted simple graph $G = (V, E)$ and a subset of
edges $X$ and asks for a shortest cycle, not necessarily simple, such that
every edge of $X$ has an endpoint in the cycle.
  We show that the decision version of the problem is strongly NP-complete,
even if $G$ is a grid graph. Regarding approximate solutions, we show that the
general case of the problem is APX-hard, and thus no PTAS is possible unless P
$=$ NP. Despite the hardness of approximation, we show that given any
$\alpha$-approximation algorithm for metric TSP, we can build a
$3\alpha$-approximation algorithm for our optimization problem, yielding a
concrete $9/2$-approximation algorithm.
  The grid case is of particular importance, because it models a city map or
some part of it. A usual scenario is having some neighborhood full of
customers, which translates as an instance of the abstract problem where almost
every edge of $G$ is in $X$. We model this property as $|E - X| = o(|E|)$, and
for these instances we give a $(3/2 + \varepsilon)$-approximation algorithm,
for any $\varepsilon > 0$, provided that the grid is sufficiently big.
