Linear Programming and Greedy Approaches for Sequence Operations
Linear Programming Formulation Let (\cdot) denote the dot product, with (b,c,x,y) as row vectors. For matrix (A), vectors (u,v) satisfy (u \leq v) if (\forall i, u_i \leq v_i), and similar for (\geq). The standard linear programming (LP) problem is: [\max c \cdot x \quad \text{s.t.} \quad \begin{cas...