Beyond Shortest Paths: Node Fairness in Route Recommendation

Speaker(s)

Ewa Kaluś

Affiliation

MIMUW

Language of the talk

Polish

Date

Jan. 20, 2026, 10:15 a.m.

Room

room 4060

Title in English

Beyond Shortest Paths: Node Fairness in Route Recommendation

Seminar

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

Podczas seminarium przedstawię pracę "Beyond Shortest Paths: Node Fairness in Route Recommendation" (VLDB 2025) (https://www.vldb.org/pvldb/vol18/p3230-ferrara.pdf}. Autorzy pracy wskazują ważny problem w systemach nawigacyjnych: gdy wszyscy użytkownicy otrzymują tę samą najkrótszą trasę, punkty położone poza nią otrzymują znacznie mniejszy ruch. Rozwiązaniem są forward paths - ścieżki, które z każdym krokiem przybliżają do celu oraz są niewiele dłuższe od najkrótszej, lecz przechodzą przez o wiele więcej wierzchołków. Omówię algorytm wykorzystujący programowanie liniowe do wyznaczenia rozkładu prawdopodobieństwa nad tymi trasami, który maksymalizuje minimalną szansę odwiedzenia każdego wierzchołka. Na koniec przedstawię wyniki eksperymentów na rzeczywistych sieciach dróg, pokazujące jak algorytm radzi sobie w porównaniu z klasycznymi podejściami.

---