Grokking pseudo-code for solution to gas station problem

Question

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill or not to Fill: The Gas Station Problem. The algorithm is reproduced below for ease of reference:

There are some obvious things to fix here in any implementation of the algorithm.

• The case $q = 1$ needs special consideration as noted by j_random_hacker in this CS SE answer.
• It may happen that no $v$ satisfies $g \leq d_{uv}$ so that there is no vertex to pick in line 10 of the algorithm. In this case, the table entry should be declared infinite, $C[u, q, g] = \infty$.

Even with those two fixes, though, it seems to me that something is still off. As the description supporting the algorithm notes, cases where $c(v) \leq c(u)$ should only be considered when $g \leq d_{uv}$, hence the special treatment in lines 9 and 10, but this additional constraint can be ignored when $c(v) > c(u)$ (according to the formula for $A(u, q, g)$ preceding Theorem 2.2). In practice, this means that the generated program does not match the recurrence relation: Below is a rough Python implementation of lines 7--11 of Fill-Row (after r has been sorted):

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while g > d[v] - d[u]:
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

If this implementation is assumed to be a correct implementation of the pseudo-code, it is easy to generate examples where $C[(u, q, g)]$ does not match $A(u, q, g)$.

A first attempt at fixing this would be to ignore $g \leq d_{uv}$ for $c(v) > c(u)$:

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

This seems to work, in that I haven't been able to construct a counter-example. Yet it seems to me that it shouldn't: If $c(v) > c(u)$ occurs for low values of $\mathrm{indep}[v]$, we risk skipping them for all but the smallest $g \in GV[u]$. As such, I would expect that we should rather reset the loop over r ($R$ in the paper) for each iteration, moving the first two lines inside the loop over GV[u]:

for g in GV[u]:
    i = 0
    v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

However, doing so takes us from $O(n \log n)$ to $O(n^2)$, which invalidates Theorem 2.2. You can probably do something more clever by keeping track of the cases $c(v) > c(u)$ and $c(v) \leq c(u)$ separately, but that doesn't seem to be in the spirit of the pseudo-code (and in particular, I'm aware that an algorithm with lower complexity exists in A fast algorithm for the gas station problem, so that clearly we can do something to remedy this), so I'm simply wondering: Am I misreading the pseudo-code?

Answer 1

The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.