1
$\begingroup$

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:

enter image description here

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.