2 papers
cs.DS2025
Logarithmic Approximation for Road Pricing on Grids
Andrei Constantinescu, Andrzej Turko, Roger Wattenhofer
Consider a graph and some commuters, each specified by a tuple consisting of two nodes in the graph and a non-negative real number , specif…
cs.GT2023
Sublogarithmic Approximation for Tollbooth Pricing on a Cactus
Andrzej Turko, Jarosław Byrka
We study an envy-free pricing problem, in which each buyer wishes to buy a shortest path connecting her individual pair of vertices in a network owned by a single vendor. The vendo…