Skip to main content
added 50 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Confirmed for $n \le 20$I confirmed via integer linear programming that the maximum value is $2k(n-k)$ for $n \le 20$ and $k>n/2$. The formulation is the same as in my answer to the linked question, except for the following changes:

  • The node set is $N = \{1,\dots,2n\}$.
  • The candidate edge set is $E = \{i \in N, j \in N: i \le n < j\}$.
  • Constraints $(3)$ and $(4)$ become \begin{align} k - (d_i - d_j) &\le (k + n) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align}

Confirmed for $n \le 20$ via integer linear programming. The formulation is the same as in my answer to the linked question, except for the following changes:

  • The node set is $N = \{1,\dots,2n\}$.
  • The candidate edge set is $E = \{i \in N, j \in N: i \le n < j\}$.
  • Constraints $(3)$ and $(4)$ become \begin{align} k - (d_i - d_j) &\le (k + n) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align}

I confirmed via integer linear programming that the maximum value is $2k(n-k)$ for $n \le 20$ and $k>n/2$. The formulation is the same as in my answer to the linked question, except for the following changes:

  • The node set is $N = \{1,\dots,2n\}$.
  • The candidate edge set is $E = \{i \in N, j \in N: i \le n < j\}$.
  • Constraints $(3)$ and $(4)$ become \begin{align} k - (d_i - d_j) &\le (k + n) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align}
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Confirmed for $n \le 20$ via integer linear programming. The formulation is the same as in my answer to the linked question, except for the following changes:

  • The node set is $N = \{1,\dots,2n\}$.
  • The candidate edge set is $E = \{i \in N, j \in N: i \le n < j\}$.
  • Constraints $(3)$ and $(4)$ become \begin{align} k - (d_i - d_j) &\le (k + n) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align}