# Grokking pseudo-code for solution to gas station problem

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?

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$$.