This is a correctly tagged repost of my question I asked yesterday.
I came across the following problem:
Given a finite grid in $\mathbb{N}^2$ (or equivalently $\mathbb{Z}^2$) consisting of $a$ rows and $b$ columns and some natural number $n$ such that $n^2 \leq ab$, which $n^2$ grid points should be marked so that the $L^1$-distance (sum of absolute coordinate differences) between a point drawn uniformly at random from the rectangle and the closest marked point is minimal on average?
To clarify as this was asked in the comments: If $(X,Y)$ are the uniformly distributed coordinates on the given grid, I would like to minimize
$$ \operatorname{E} \left( \min_{(x,y)}\left( | X-x | + |Y-y| \right) \right), $$
where the minimum is taken over all $n^2$ marked points with coordinates $(x,y)$.
When $a=b$, intuition tells me that the solution should be an evenly spaced and symmetric $n \times n$ grid with the same center as the original grid, but even this I'm not able to prove. In the the general case, it is further not clear to me if the optimal marking should form a grid at all (a crucial role should be played by the "aspect ratio" $a/b$).
Is this a standard problem and if so, where could I read about it?
In case it makes the solution easier: In the application I need this for, $n^2$ is several orders of magnitude smaller than $ab$.
This is a cool but hard problem you have there. If it's been solved, it's certainly not found in combinatorial optimization textbooks... Good luck finding a paper that solves the problem.
For a fixed $W$, you can check if a configuration of $n^2$ "sites" yielding objective value less then $W$ exists, as follows:
Build a graph who's vertices are your gird-points and connect them by an edge if their $L^1$ distance is less then $W$. Next, look for a minimum cardinality vertex cover on this graph: this is an NP-complete task, but you can use approximation algorithms or efficient exact exponential algorithms for the problem available, as minimum vertex cover is well studied. If the minimum vertex cover has size greater then $n^2$, no interesting conclusion can be drawn. But if the vertex cover has size less then $n^2$, you know that any point on the grid has distance less then $W$ to at least one of these points (by our construction of edges and definition of a vertex cover), so that its $L^1$ distance to the cover $C$ is less then $W$.
The expectation you're trying to minimize is $E= \sum _{ij} P(ij)\cdot dist_{L^1} (ij,C)$, where $P(ij)$ is the probability of landing on grid-point $ij$. So for the cover, since $dist_{L^1} (ij,C) \leq W$, bounding and sumation of the probability measur gives $E\leq W$.
You can then proceed binary-search-style for checks on $W$. Start with upper bound $U=ab$ and lower bound $L=0$ and get lower and upper bounds as follows. If there is a vertex cover of size less then $n^2$ for $U$, check if there is one for $\frac{U+L}{2}$: if so, set the new upper bound to $\frac{U+L}{2}$ and repeat, else set the lower bound to $\frac{U+L}{2}$ and repeat. Stop whenever you feel like the difference between upper and lower bound is small enough. This should provide a decent approximation of your objective...
The problem seems so symmetric that it feels like there should be formulas for the optimal solutions, at least for uniform probability... But finding and proving that seems really hard.