I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly appreciated and I would appreciate you providing me with relevant papers as well.

Context: I am trying to give an algorithm related to graph theory. Unfortunately, my knowledge of LP is very limited that is why I need your guidance. In the following algorithm $ 2k$ is the degree of the investigated vertex. Ideally, I am looking for $ O(k)$ or $ O(k \log k)$ solution, or in total $ O(n)/O(n\log n)$ when this applies to all the vertices. Note that $ |E|= O(n)$ . However, any fast algorithm would be appreciated.

**Minimize:** $ T$

**Subject to:**

$ \forall i \in [2k] \qquad 1 \le t_i \le 2k$

*Comment: Ensuring that $ \forall i, j \in [2k],\ i \neq j \qquad |t_i – t_j| \ge 1$ *

*Comment: I want $ t_i$ ‘s to be distinct positive integers in [2k]*

$ \forall i, j \in [2k],\ i \neq j \qquad 1 \ge t_i – t_j$

$ \forall i, j \in [2k],\ i \neq j \qquad 1 \ge t_j – t_i$

$ \forall i \in [2k],\ i \text{ is an odd number} \qquad t_i \le t_{i+1}$

$ \forall i \in [k] \qquad 0 \le x_i \le 1$

$ \forall i \in [k] \qquad \text{A linear constraint}\ F(x_i,\ t_{2i},\ t_{2i-1},\ T)$