Consider bipartite graph with vertex set $V\_1\cup V\_2$ where $|V\_1|=\frac{n(n-1)}2$ and $|V\_2|=n$. The vertices in $V\_1$ all have degree $2$ and connected to two vertices in $V\_2$. The vertices in $V\_2$ all have degree $n-1$ and connected to $n-1$ vertices in $V\_1$.


I have integers $2^m<a\_1,\dots,a\_{\frac{n(n-1)}2}<2^{m+1}$ where $m\in\Bbb N$ assigned to each vertex in $V\_1$. At every $i\in\Big\{1,\dots,\frac{n(n-1)}2\Big\}$ denote $r(i)$ and $s(i)$ to be two vertices in $V\_2$ that are connected to $a\_i$. I want to have $b\_1,\dots,b\_n\in\Bbb R$ assigned to vertices in $V\_2$ such that $$J=\sum\_{i=1}^{\frac{n(n-1)}2}(a\_i-(b\_{r(i)}+b\_{s(i)}))^2$$ is minimized.


**(1)** Can this always be done in time $(nm)^c$ for some fixed $c\in\Bbb R$?


**(2)** What is the distribution of $J$ among all assignments of $a\_i$? For instance can $J\leq\frac{n(n-1)}2m^\alpha$ and $\max\_{i\in\{1,\dots,\frac{n(n-1)}2\}}(a\_i-(b\_{r(i)}+b\_{s(i)}))^2\leq m^\alpha$ where $\alpha\in\Bbb R$ is fixed be possible with probability $1-\frac1{nm}$ where $a\_i$'s are picked uniformly independently?



A graph assignment problem
I'm going to change notation a little, using $a\_{jk}$ instead of $a\_i$ for the vertex $i$ with $r(i)=j$ and $s(i)=k$, and $x\_i$ instead of $b\_i$. The objective function is
$$ J(\boldsymbol{x}) = \sum\_{1\le j\lt k\le n} (a\_{jk}-(x\_j+x\_k))^2. $$
Minimizing a quadratic form is standard stuff, see for example [this description](http://www.cis.upenn.edu/~cis515/cis515-11-sl12.pdf) (Prop. 12.2).
Write the expression in the standard form
$$J(\boldsymbol{x}) = \tfrac12 \boldsymbol{x}^T A\boldsymbol{x} - \boldsymbol{b}^T\boldsymbol{x} + c$$
with $A$ symmetric.
You will find that the matrix $A$ has diagonal entries $2(n-1)$ and off-diagonal entries $2$, so it is positive-definite and its inverse has the same form (constant diagonal and constant off-diagonal). The minimum value then occurs with $\boldsymbol{x}=A^{-1}\boldsymbol{b}$ and has value
$$-\tfrac12\boldsymbol{b}^TA^{-1}\boldsymbol{b} + c.$$
Given the simple form of $A^{-1}$ you can write this as a sum over entries of $\boldsymbol{b}$.


I'll let you take it from there.


