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.

Modification and Clarifications (Edit):
There was a mistake as pointed out by @D.W. I changed the program. Beside $t_i$'s which I need to be distinct positive integers between $1$ to $2k$, there are variables $x_i$'s and $T$. Originally, I want $T$ to be an integer and $x_i$ to be $0$ or $1$; however, it is not important. If we find an optimal solution in which $T$ and $x_i$'s are real values I have a $O(k)$ mechanism to find the solution I want based on it. Do we have a polynomial solution to this program? (based on $n$, number of vertices.) (Any other LP comes to mind such that it forces $t_i$ condition but does not make it Integer Program?)

Minimize: $T$
Subject to:
$\forall i \in [2k] \qquad t_i \in \mathbb{N},\ \ 1 \le t_i \le 2k$
$\forall i, j \in [2k], i \neq j \qquad t_i \neq t_j$

$\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)$
Comment: If it helps, $F(x_i,\ t_{2i},\ t_{2i-1},\ T)$ is $(1-x_i)(T-t_{2i-1}+1\ +\ T-t_{2i}+1)\ +\ (x_i)(T-t_{2i-1}+1) \ge |C_i| - 1$, Where $|C_i|$ is a constant I know.

  • $\begingroup$ It is unclear exactly what you are trying to solve and how the problem is defined. For example, what is $T$? Basically, your problems is going to be one of the followings: a network flow problem, a linear program with only continuous variables, or an integer linear program. Each of them can be solved with a specialized solver $\endgroup$ – Gabriel Gouvine Jun 15 at 19:20
  • $\begingroup$ Do you require that any/all of the $t_i,x_i,T$'s be integers? What is $F$? $\endgroup$ – D.W. Jun 15 at 19:56
  • 1
    $\begingroup$ Your constraints are contradictory. Your comment says $|t_i-t_j| \ge 1$, but your inequalities have inequality go the other direction. $\endgroup$ – D.W. Jun 15 at 19:57
  • 1
    $\begingroup$ As stated, your constraint is quadratic, not linear $\endgroup$ – Gabriel Gouvine Jun 15 at 22:44
  • 1
    $\begingroup$ It's also not a linear program; it's an integer linear program (which also tends to be much harder than a linear program). $\endgroup$ – D.W. Jun 15 at 23:21

Your Answer

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

Browse other questions tagged or ask your own question.