Return to Question

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$?

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?

I have a 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 integers $b_1,\dots,b_n$ 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$?

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$?

I have a 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 $a_1,\dots,a_{\frac{n(n-1)}2}$ 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 integers $b_1,\dots,b_n$ assigned to vertices in $V_2$ such that at every $i\in\Big\{1,\dots,\frac{n(n-1)}2\Big\}$ $$a_i=b_{r(i)}+b_{s(i)}$$

(1) Can this always be done and if not what constraints on $a_i$ we need to have such an assignment?

(2) Is there a good technique to find assignment in $V_2$ that assigns in time $n^c$ for some fixed $c\in\Bbb R$?

I have a 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 integers $b_1,\dots,b_n$ 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$?