Can I read A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond on EtoBox?

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond by Nägele, Martin; Zenklusen, Rico is a scholarly article available to read on EtoBox.

What is A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond about?

Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in cuts forming a laminar family of small width. Our main contribution is a new dynamic programming approach where the value of a table entry does not only depend on the values of previous table entries, as it is usually the case, but also on a specific representative solution saved together with each table entry. This allows for handling a broad range of constraint types. In combination with other techniques -- including negatively correlated rounding and a polyhedral approach that, in the problems we consider, allows for avoiding potential losses in the objective through the randomized rounding -- we obtain several new results. We first present a quasi-polynomial time algorithm for the Minimum Chain-Constrained Spanning Tree Problem with an essentially optimal guarantee. More precisely, each chain cons

Author

Nägele, Martin; Zenklusen, Rico

Published

2023

Language

EN