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

The concept of bounded highway dimension was developed to capture observedproperties of the metrics of road networks. We show that a graph with boundedhighway dimension, for any vertex, can be embedded into a a graph of boundedtreewidth in such a way that the distance between $u$ and $v$ is preserved upto an additive error of $\epsilon$ times the distance from $u$ or $v$ to theselected vertex. We show that this theorem yields a PTAS for Bounded-CapacityVehicle Routing in graphs of bounded highway dimension. In this problem, theinput specifies a depot and a set of clients, each with a location and demand;the output is a set of depot-to-depot tours, where each client is visited bysome tour and each tour covers at most $Q$ units of client demand. Our PTAS canbe extended to handle penalties for unvisited clients.  We extend this embedding result to handle a set $S$ of distinguishedvertices. The treewidth depends on $|S|$, and the distance between $u$ and $v$is preserved up to an additive error of $\epsilon$ times the distance from $u$and $v$ to $S$.  This embedding result implies a PTAS for Multiple Depot Bounded-CapacityVehicle Routing: the tours can go from one depot to another. The embeddingresult also implies that, for fixed $k$, there is a PTAS for $k$-Center ingraphs of bounded highway dimension. In this problem, the goal is to minimize$d$ such that there exist $k$ vertices (the centers) such that every vertex iswithin distance $d$ of some center. Similarly, for fixed $k$, there is a PTASfor $k$-Median in graphs of bounded highway dimension. In this problem, thegoal is to minimize the sum of distances to the $k$ centers.

Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension