All Questions

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?

Consider the set of constraints of the uncapacitated lot sizing problem: $$ \{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...