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 study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths problem (EDP), we are given a network G with source-sink pairs (si; ti), 1 i k, and the goal is to nd a largest subset of source-sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any > 0, EDP is NP-hard to approximate within m 1=2 . We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any > 0, bounded length EDP is hard to approximate within m 1=2 even in undirected networks, and give an O( p m)-approximation algorithm for it. For directed networks, we show that even the single source-sink pair case (i.e. nd the maximum number of paths of bounded length between a given sourcesink pair) is hard to approximate within m 1=2 , for any > 0.

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems