English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the bi-criteria shortest-path problem where we want to computeshortest paths on a graph that simultaneously balance two cost functions. Whilethis problem has numerous applications, there is usually no path minimizingboth cost functions simultaneously. Thus, we typically consider the set ofpaths where no path is strictly better then the others in both cost functions,a set called the Pareto-optimal frontier. Unfortunately, the size of this setmay be exponential in the number of graph vertices and the general problem isNP-hard. While existing schemes to approximate this set exist, they may beslower than exact approaches when applied to relatively small instances andrunning them on graphs with even a moderate number of nodes is oftenimpractical. The crux of the problem lies in how to efficiently approximate thePareto-optimal frontier. Our key insight is that the Pareto-optimal frontiercan be approximated using pairs of paths. This simple observation allows us torun a best-first-search while efficiently and effectively pruning awayintermediate solutions in order to obtain an approximation of the Paretofrontier for any given approximation factor. We compared our approach with anadaptation of BOA*, the state-of-the-art algorithm for computing exactsolutions to the bi-criteria shortest-path problem. Our experiments show thatas the problem becomes harder, the speedup obtained becomes more pronounced.Specifically, on large roadmaps, we obtain an average speedup of more than$\times 8.5$ and a maximal speedup of over $\times 148$.

Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier