Informally speaking, if $n$ people living at the vertices of the $m$-dimensional unit cube $C_m$ want to have a party at the most convenient vertex of $C_m$ (possibly at one of the $n$ vertices themselves), what is the worst case maximum distance in terms of $m$ and $n$ that any one of them may have to travel in the "Manhattan" or $\ell_1$ metric (that is: along the edges of the cube). Note that this is referring to the best choice of party venue subject to the minimisation of the longest journey, with the worst-case distribution of people in that regard
Formally speaking, I'm defining $D_{m,n} \in \mathbb{N}$ to be minimal such that the following is true: $$\forall x_1, x_2, ..., x_n \in C_m ~ \exists ~ c\in C_m ~\forall~ 1\leq i \leq n: d_1(x_i,c) \leq D_{m,n}$$ where $(C_m,d_1)$ is the metric subspace $\lbrace0,1\rbrace^m$ of $(\mathbb{R}^m,||\cdot||_1)$.
My limited progress so far:
By the triangle inequality, I can see that $D_{m,2}=\lceil\frac{m}{2}\rceil$. I can see it can't be any smaller in the case $x_1=(0,0,...,0), x_2=(1,1,...,1)$.
The simple example for $m=2$ and $n=4$ where the $x_i$ are all the different vertices of the square shows that $D_{2,4}=2 > D_{2,2}=1$. So $D_{m,n}$ definitely somehow increases with $n$ if $m$ is held constant. I just don't quite see how. For example, I haven't yet managed to construct a distribution showing that $D_{12,4}>6=D_{12,2}$.
I'd be grateful for any suggestions of a way to think about this systematically without exhaustive simulation!
By a Chernoff bound, the fraction of locations within $\frac m2 + k \sqrt{\frac m2}$ steps of a given attendee is $p \le e^{-k^2/3}$. Thus, if you have fewer than $e^{k^2/3}$ attendees, you will be able to find a location within $\frac m2 + k\sqrt{\frac m2}$ steps of each of them.
Also, if we put down $n$ attendees at random vertices of the cube, then for each location, the probability that it's within $\frac m2 + k\sqrt{\frac m2}$ steps of each of them is $(1-p)^n < e^{-pn}$, so if we set $n = \frac{m \ln 2}{p}$, this probability is less than $2^{-m}$. Then the expected number of locations that work is less than $1$, so there is some choice of $ \frac{m \ln 2}{p}$ attendees for which no location is this convenient.
So whatever the actual value of $p$ is for a given $m$ and $k$, we have $$ D_{m, 1/p} \le \frac m2 + k\sqrt{\frac m2} \quad \text{and} \quad D_{m,m\ln 2/p} \ge \frac m2 + k\sqrt{\frac m2}. $$ If we fix $k$ and let $m \to\infty$, then $p \to \frac{1-\text{erf}(k)}{2}$, where erf is the error function.