Abstrakt. Vi anser att beräkningen av min-kostnadsvägar i tidsberoende nätverk, vars bågar lyder kontinuerliga, bitvis linjära, periodiska, FIFO-kompatibla, båge-kostnad funktioner i den faktiska tiden för användning av varje båge. Att beräkna tidsberoende min-kostnadsvägar i sådana nätverk för alla möjliga tider är en ganska svår utmaning, eftersom det har utrymme-komplexitet på (1 + K * ) · n  på (log n), där n är antalet hörn och K * är antalet koncavity-spoiling brytpunkter i båge-kostnadsfunktioner. Om (1 + ε)-ungefärliga min-kostnadsvägar är godtagbara, då ett nyligen resultat visade att tidsberoende orakel kan beräknas i O n 2−a (K * + 1) utrymme, för vissa en 0, 1), och kan svara på frågor (under vissa villkor) i O n b tid, för vissa b  till (0, 1). När K * o(n) kan oraklet finjusteras så att både frågetiden är sublinjär och utrymmet är subkvadratiskt i n. En huvudutmaning är att tillhandahålla orakler för tidsberoende nätverk, som uppnår (i) subkvadratiskt förbearbetningsutrymme och tid oberoende av K *, som i allmänhet kan vara  och (n), och (ii) frågesvar gånger sublinjär, inte bara i det värsta fallet (dvs., i n), men också i antalet λ av etablerade hörn med Dijkstra algoritm tills destinationen är avvecklad (Dijkstra-rank). I detta arbete tar vi på ett positivt sätt itu med den ovannämnda utmaningen. I synnerhet tillhandahåller vi: (i) En ny effektiv algoritm (TRAP) för att konstruera one-to-all (1 + ε)-sammanfattningar av min-cost funktioner, för ett godtyckligt ursprung. Nyheten med denna algoritm är att den inte kräver konkaviteten hos den okända funktionen för att approximera, och att de konstruerade funktionerna har en koncist representation som är oberoende av K *. (ii) FLAT oraklet, som kombinerar TRAP tillsammans med en annan approximationsalgoritm, för att konstruera sammanfattningar från slumpmässigt utvalda landmärken till alla tillgängliga destinationer. Den förbehandlade datastrukturen uppnår mellanslag O n 2−δ polylog(n), för vissa δ  till (0, 1), d.v.s. subquadratic och oberoende av K *, medan fortfarande njuta av en frågetid av O n b för vissa b  till (0, 1). (iii) HORN oraklet, som organiserar en geometriskt minskande hierarki av landmärken, från lokala landmärken har sammanfattningar endast för små stadsdelar av destinationer runt omkring dem, upp till globala landmärken har sammanfattningar för alla nåbara hörn. Tid- och rymdkraven för HORN är återigen subkvadratiska och jämförbara med dem för FLAT inom polylogaritmiska faktorer. Vi utformar och analyserar sedan en ny frågealgoritm, som utnyttjar den landmärkeshierarkin för att ge en frågetid av O Ε b, för några b 0, 1), det vill säga sublinear i den faktiska Dijkstra-rank av frågan till hands. Preliminära experiment på verkliga nätverk visar ett utmärkt resultat av de nya oraklerna i praktiken.
Vårt andra bidrag är genomförandet och den experimentella utvärderingen av den nya HORN oracle REF, som bygger på en hierarki av landmärken, från några "globala" landmärken med kunskap om hela nätverket mot (många fler) "lokala" landmärken vars kunskap om nätverket är begränsad till små stadsdelar runt omkring dem.
Hierarchical Oracles for Time-Dependent Networks.
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}