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 present a unified polynomial-time approximation scheme (PTAS) for theprize collecting traveling salesman problem (PCTSP) and the prize collectingSteiner tree problem (PCSTP) in doubling metrics. Given a metric space and apenalty function on a subset of points known as terminals, a solution is asubgraph on points in the metric space, whose cost is the weight of its edgesplus the penalty due to terminals not covered by the subgraph. Under ourunified framework, the solution subgraph needs to be Eulerian for PCTSP, whileit needs to be connected for PCSTP. Before our work, even a QPTAS for theproblems in doubling metrics is not known.  Our unified PTAS is based on the previous dynamic programming frameworksproposed in [Talwar STOC 2004] and [Bartal, Gottlieb, Krauthgamer STOC 2012].However, since it is unknown which part of the optimal cost is due to edgelengths and which part is due to penalties of uncovered terminals, we need todevelop new techniques to apply previous divide-and-conquer strategies andsparse instance decompositions.

A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics