Solving a problem with linear programming

Question

Suppose we wish to create a speech. Assume we have $n$ words to choose from numbered from 1ドル$ to $n$. Every word holds a list of words that can come after it $S_i$. For example: if 2ドル \in S_1$ then the speech can contain the sequence of words 1,2ドル$. Every word has a length $n_i$ and a positive weight $w_i$ signifying how 'effective' this word is to the crowd.

Describe an algorithm, as efficient as possible finding a speech of exactly $l$ letters of maximal weight, given the linguistic constraints as were denoted.

For runtime complexity purposes assume $\sum S_i = s$.

---

An algorithm solving this in linear time is emitted using DFS. Even so, I noticed this question is very simple to define as an LP and I wondered if it can have an efficient solution. I have provided a layout of a possible linear program. I'd like to know if this question can be solved efficiently using LP.

---

So I've thought of a way to compute this using a graph $G=(V,E)$ s.t:

1. $V = \{s,t\} \cup[n]\times[l]\cup\{0\}$
2. $E=\{((s,0),(i,n_i))|n_i\leq l\}\cup\\\quad\quad \{((i,m),(j,m+n_j))|j\in S_i\land m+n_j \leq l\}\cup\\\quad\quad\{((i,l),(t,0))|i\in[n]\}$
3. The weight function is the $w'$ is $-w$ for all edges except the ones entering $t$ which will be 0.

This is a DAG and thus i can find SSSP from $s$ to $t$ in $\approx O(n+s)$.

Now say i module the problem in the following manner:

Look for a vector $x$ s.t we maximize $\sum x_iw_{x_i}$ whilst holding:

1. $\sum n_{x_i}=l$
2. $x_i \in [n]$

Now I can transform this into standard form and run simplex algorithm.

Thanks in advance!

• codeR: You might want to explore interior point algorithms, namely the Karmarkar's algorithm which has polynomial running time for solving an LP.
• MathStudent101: @codeR unfortunately we aren't covering this topic in the course I'm taking.
• codeR: Then you may carefully generate instances where Simplex terminates in polynomial time.
• D.W.: 1. Where did you encounter this task? Can you credit the original source? 2. Why do you require that it be solved with linear programming? Linear programming seems like a poor fit for this task. This seems like an XY problem.
• MathStudent101: @D.W.I received this question as homework so I don't have any reference unfortunately. I don't require to solve this with LP (and I provided other solution). It was just so easy to define the problem as LP that I was hoping I can achieve a good runtime. I guess that I was wrong. Thanks!