Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty

2022/11/28 by Corinna Mathwieser, Mathwieser, Corinna, Eranda Çela +1 · 2 citations
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2211.15611

openalex publication_date 2022/11/28 · openalex created_date 2022/12/10 · openalex updated_date 2026/07/28

Abstract

This article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special instance types, including cactus graphs, for which we provide randomized algorithms. We introduce the problem of finding a minimum weight spanning star under uncertainty for which we show that no algorithm can achieve constant competitive ratio.

Cited by

• Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
• On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms

Related

• On the approximability of robust spanning tree problems
• Connectivity graphs of uncertainty regions
• Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
• Online Minimum Spanning Trees with Weight Predictions
• A randomized linear-time algorithm to find minimum spanning trees