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 develop fast approximation algorithms for the minimum-cost version of theBounded-Degree MST problem (BD-MST) and its generalization the CrossingSpanning Tree problem (Crossing-ST). We solve the underlying LP to within a$(1+\epsilon)$ approximation factor in near-linear time via the multiplicativeweight update (MWU) technique. This yields, in particular, a near-linear timealgorithm that outputs an estimate $B$ such that $B \le B^* \le \lceil(1+\epsilon)B \rceil +1$ where $B^*$ is the minimum-degree of a spanning treeof a given graph. To round the fractional solution, in our main technicalcontribution, we describe a fast near-linear time implementation ofswap-rounding in the spanning tree polytope of a graph. The fractional solutioncan also be used to sparsify the input graph that can in turn be used to speedup existing combinatorial algorithms. Together, these ideas lead tosignificantly faster approximation algorithms than known before for the twoproblems of interest. In addition, a fast algorithm for swap rounding in thegraphic matroid is a generic tool that has other applications, including to TSPand submodular function maximization.

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems