Logarithmic Approximation for Road Pricing on Grids

Andrei Constantinescu, Andrzej Turko, Roger Wattenhofer

Consider a graph $G=(V,E)$ and some commuters, each specified by a tuple $(u,v,b)$ consisting of two nodes in the graph $u,v\in V$ and a non-negative real number $b$, specif…