Finding a better bound for $c$ such that: $\sum_{i=1}^n{w_i}<\sum_{i=1}^n{w_i'}\implies\sum_{i=1}^n{w_i^2}<c\cdot \sum_{i=1}^n{w_i'^2}$

Question

I am trying to solve the assignment problem between 2 sets of $n$ points in $\mathbb{R}^d$ minimizing the sum of square distances, i.e. finding a pairing between the two sets such that each point is mapped to exactly one point from the other set and minimize the sum of square distances.

There are many fast solutions for the problem for the case of minimizing distances instead of squared distances, unfortunately there aren't such fast solutions for the squared distances case (at least that I know of) so I was wondering if I'll just use the sum of distances algorithm would that give me a constant approximation for the squared distances case. I.e, if the weights in the optimal sum distances case are $w_1,...w_n$ and in the squared distances case are $w_1',...,w_n'$ is it true that:

$$\sum_{i=1}^n{w_i}<\sum_{i=1}^n{w_i'}\implies\sum_{i=1}^n{w_i^2}<c\cdot \sum_{i=1}^n{w_i'^2},$$

where $c<<n$.

Edit:

I was able to prove this for $c=n$ using Equivalent norm properties (see https://en.wikipedia.org/wiki/Norm_(mathematics)#Equivalence): $$\sum_{i=1}^{n}{w_i^2}\leq\left(\sum_{i=1}^{n}{w_i}\right)^2\leq\left(\sum_{i=1}^{n}{w_i'}\right)^2=\left\lVert w'\right\rVert_1^2\leq n\left\lVert w'\right\rVert_2^2=n\cdot \sum_{i=1}^{n}{w_i'^2},$$

but I wanted to know if there's something better than $n$.

Answer 1

Lets see why we cannot in general take e.g. $c < \frac{n}{1.21}$.

Let $w_1',\ldots, w_n'=\frac{1.1}{n}$ and $w_1 =1, w_2=\ldots = w_n=0$. Then $\sum w_i = 1 < \sum w'_i =1.1$ but $\sum w_i^2 = 1$ with $\sum w_i'^2 = \frac{1.21}{n}$. Thus $c> \frac{n}{1.21}$, and similarly $c > \gamma n$ for all $\gamma < 1$.

So without further knowledge, such a general $c$ must be at least $n$, otherwise the norm property that you reference could also just be improved in a general setting.

Answer 2

This might not be the best result, but at least it puts some bound on things......
I claim that with all $w_i, w_i' \ge 0$
$\sum_{i=1}^n{w_i}<\sum_{i=1}^n{w_i'}\implies\sum_{i=1}^n{w_i^2} \le n^3\cdot \sum_{i=1}^n{w_i'^2}$
Proof:
For each $i$ we have $w_i \le \sum_{i=1}^n{w_i'} \le n.W'$ where $W' = max\{w_i'\}$
So with $w_i \ge 0$, we have $w_i^2 \le n^2W'^2$
Then $\sum_{i=1}^n{w_i^2} \le n.n^2 W'^2 = n^3 W'^2 $
And $W'^2 \in \{w_i'^2\}$ so $ W'^2 \le \sum_{i=1}^n{w_i'^2}$
Then $\sum_{i=1}^n{w_i^2} \le n^3 \sum_{i=1}^n{w_i'^2}$

(to get a strict inequality, add some small $\epsilon$ to $n^3$)