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

Short spanning trees subject to additional constraints are important buildingblocks in various approximation algorithms. Especially in the context of theTraveling Salesman Problem (TSP), new techniques for finding spanning treeswith well-defined properties have been crucial in recent progress. We considerthe problem of finding a spanning tree subject to constraints on the edges incuts forming a laminar family of small width. Our main contribution is a newdynamic programming approach where the value of a table entry does not onlydepend on the values of previous table entries, as it is usually the case, butalso on a specific representative solution saved together with each tableentry. This allows for handling a broad range of constraint types.  In combination with other techniques -- including negatively correlatedrounding and a polyhedral approach that, in the problems we consider, allowsfor avoiding potential losses in the objective through the randomized rounding-- we obtain several new results. We first present a quasi-polynomial timealgorithm for the Minimum Chain-Constrained Spanning Tree Problem with anessentially optimal guarantee. More precisely, each chain constraint isviolated by a factor of at most $1+\varepsilon$, and the cost is no larger thanthat of an optimal solution not violating any chain constraint. The bestprevious procedure is a bicriteria approximation violating each chainconstraint by up to a constant factor and losing another factor in theobjective. Moreover, our approach can naturally handle lower bounds on thechain constraints, and it can be extended to constraints on cuts forming alaminar family of constant width.  Furthermore, we show how our approach can also handle parity constraints (or,more precisely, a proxy thereof) as used in the context of (Path) TSP and oneof its generalizations, and discuss implications in this context.

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond