2
$\begingroup$

You have a table with two rows and $k$ columns. The cells are filled with nonnegative real numbers so that the sum of the numbers in each row is $1$.

Call the sum of the largest number in each column $X$ (so $X$ is a sum of $k$ numbers, one per column).

Color one number in each column, so that for each row, the sum of the colored numbers is at least the sum of the uncolored numbers, if we're allowed to remove an uncolored number of our choice. Call the maximum possible sum of the colored numbers $Y$.

What is the largest possible ratio $\frac{X}{Y}$?

On the one hand, the ratio cannot be larger than $1.5$. This is because if, in $X$, the sum of the colored numbers in each row is at least $0.5$, then $X=Y$. If not, $X\leq 1.5$, and we can check that $Y\geq 1$.

$\endgroup$
  • 2
    $\begingroup$ Could you define $X$ without colorings as the sum of the largest elements per column, or are the colorings for $X$ and $Y$ connected? You define $Y$ as the maximum possible sum, but did you mean minimum? Otherwise I do not see why $Y<X$. $\endgroup$ – LinAlg Dec 19 '18 at 20:04
  • $\begingroup$ $Y$ is bounded below, and if you color the largest number in each column you get $X=Y$ and the constraint is automatically satisfied. $\endgroup$ – LinAlg Dec 20 '18 at 12:08
  • $\begingroup$ Not quite. In your example you can color 0.25, 0.25, 0.25 and 0.4, so $Y=1.15$. For row 1 you get $0.75 \geq 0$ (after removing the last 0.25) and for row 2 you get $0.4 \geq 0.2 + 0.2$ (after removing one 0.2), so the coloring is valid. $\endgroup$ – LinAlg Dec 20 '18 at 19:21
1
+50
$\begingroup$

What is the largest possible ratio $\frac{X}{Y}$?

Short answer: 8/7 based on the matrix $$\begin{pmatrix}0.5 & 0.5 & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\end{pmatrix}.$$ for which you get $X=4/3$ and $Y=7/6$ (by coloring the (1,1), (2,2) and (2,3) elements).

How I found this: consider the matrix $A\in\mathbb{R}_+^{2\times k}$ with elements $a_{ij}\geq 0$. We can always permute the columns in a way that the largest numbers are in the first row for the first set of columns, and in the second row for the last set of columns. Let $p$ denote the number of columns for which the maximum is in the first row. We will consider $p=1,2,\ldots,\left \lfloor{k/2}\right \rfloor$ (due to symmetry there is no need to consider larger $p$). We have: $$X=\sum_{j=1}^p A_{1j} + \sum_{j=p+1}^k A_{2j}.$$ To further reduce symmetry, we can assume that the first $p$ columns and the last $k-p$ columns of $A$ are both sorted high to low in the first row. This symmetry breaking rule is not necessary, but helps in terms of speed (the first one is necessary for efficiently setting $X$). Let $C \subset \{0,1\}^{2 \times k}$ denote the set of $2^k$ possible colorings: for $c\in C$, $c_{ij} = 1$ if element $(i,j)$ is colored, and 0 otherwise. The following inequalities set the highest lower bound on $Y$ by enumerating all valid colorings: $$\forall c \in C : (Y \geq \sum_{ij} a_{ij} c_{ij}) \vee \sum_{j} a_{1j} c_{1j} < a_{1j} (1-c_{1j}) - a_{1j'} \forall j' \vee \sum_{j} a_{2j} c_{2j} < a_{2j} (1-c_{2j}) - a_{2j'} \forall j',$$ where $j'$ has to be an uncolored element $(c_{ij'}=0)$.

For fixed $k$, $p$ and $X$, you can minimize $Y$ via mixed integer optimization (matlab/YALMIP code below). It uses a big-M formulation for the three alternatives above. Here is the output for $k=4$:

enter image description here

If you run the code with $k$ larger than 4, you just get extra columns that are zero. Zooming in (generating more data points) shows a maximum at $X=4/3$.

k=5;
eps = 0.0001;
y = [];
for x = linspace(1,1.5,50)
    opt = 0;
    for p = 1:floor(k/2)
        yalmip('clear');
        A = sdpvar(2,k);
        Y = sdpvar(1,1);
        % nonnegative and row sum 1
        F = [A >= 0];
        F = F + [sum(A,2) == 1];
        % break symmetry
        F = F + [A(1,1:p) >= A(2,1:p)];
        F = F + [A(1,p+1:k) <= A(2,p+1:k)];
        F = F + [A(1,1:p-1) >= A(1,2:p)];
        F = F + [A(1,p:k-1) >= A(1,p+1:k)];
        % set X
        X = sum(A(1,1:p)) + sum(A(2,p+1:k));
        F = F + [X == x];
        % iterate over all colorings
        for c = (1 + dec2bin(1:2^k-2) - '0')'
            c = full(sparse(c,1:k,ones(k,1),2,k));
            % one out of three constraints
            one_out_of_three = binvar(3,1);
            F = F + [sum(one_out_of_three) == 1];
            F = F + [Y >= sum(sum(c.*A)) - k*(1-one_out_of_three(1))];
            sum_colored = sum(c.*A,2);
            sum_uncolored = sum((1-c).*A,2);
            for i = 1:2
                for j = find(c(i,:)==0)
                    F = F + [sum_colored(i) + 0.001 <= sum_uncolored(i) - A(i,j) + k*(1-one_out_of_three(1+i))];
                end
            end
        end
        optimize(F,Y, sdpsettings('verbose', 0));
        fprintf('Maximum ratio for X=%f, k=%d, p=%d: %f\n', x, k, p, double(X/Y));
        opt = max(opt, double(X/Y));
    end
    y = [y; opt];
end
plot(linspace(1,1.5,50), y, '*');
xlabel('X');
ylabel('max X/Y');
$\endgroup$
  • $\begingroup$ @pi66 you are right! I have updated the answer $\endgroup$ – LinAlg Dec 21 '18 at 17:22
  • $\begingroup$ @pi66 the last two alternatives in the $\vee$ statement are negations, so it is $\forall$ and the inequality is reversed: either $Y$ is bounded above, or the coloring is not valid $\endgroup$ – LinAlg Dec 21 '18 at 21:07
  • $\begingroup$ @pi66 so you propose to change the condition in the question into: 'for each row, the sum of the colored numbers is at least the sum of the uncolored numbers minus one uncolored number, no matter which uncolored number we leave out'? $\endgroup$ – LinAlg Dec 21 '18 at 21:47
  • $\begingroup$ @pi66 I think that my initial answer answered that question. $\endgroup$ – LinAlg Dec 21 '18 at 22:18
  • $\begingroup$ @pi66 unfortunately not. If all you have is a hammer, everything looks like a nail. $\endgroup$ – LinAlg Dec 23 '18 at 14:04
0
$\begingroup$

Before solving it, I will try to formalize this problem as an optimization problem

Calling the two rows by $R_1, R_2$ we have

$$ R_1 = \{r_1^1,r_1^2,\cdots,r_1^n\}\\ R_2 = \{r_2^1,r_2^2,\cdots,r_2^n\} $$ such that $p_i(r_i) = r_i^j \ge 0$ and $e_i(r_i) = \sum_k r_i^k = 1$ for $i = \{1,2\}$

now

$$ X(r_1,r_2) = \sum_k \max(r_1^k, r_2^k) $$

considering now $\phi$ assuming values in $\{0,1\}$ let us define

$$ f(\phi,r_1,r_2) = \sum_k \phi_k r_1^k + \bar\phi_kr_2^k $$

and the restrictions

$$ g_1(\phi,r_1) = \sum_k \phi_k r_1^k \ge \sum_k \bar\phi_k r_1^k\\ g_2(\phi,r_2) = \sum_k \phi_k r_2^k \ge \sum_k \bar\phi_k r_2^k $$

and then with

$$ Y(\phi,r_1,r_2) = \max_{\phi} f(\phi,r_1,r_2) $$

the final formulation

$$ \max_{\phi,r_1,r_2}\left(\frac XY\right) \ \ \mbox{s. t.}\ \ p_i(r_i)\cap e_i(r_i)\cap g_1(\phi,r_1)\cap g_2(\phi,r_2) $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.