Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

DOI10.1137/16M1088375zbMath1372.68294WikidataQ57399718 ScholiaQ57399718MaRDI QIDQ5283242

Nicole Megow, Martin Skutella, Julie Meißner

Publication date: 21 July 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

competitive analysisonline algorithmsminimum spanning treerandomized algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (14)

Algorithms that access the input via queries ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Two-stage robust optimization problems with two-stage uncertainty ⋮ Query-competitive sorting with uncertainty ⋮ Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments ⋮ Set selection under explorable stochastic uncertainty via covering techniques ⋮ Round-competitive algorithms for uncertainty problems with parallel queries ⋮ Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty ⋮ An adversarial model for scheduling with testing ⋮ Query minimization under stochastic uncertainty ⋮ Query-Competitive Sorting with Uncertainty. ⋮ The Minimum Cost Query Problem on Matroids with Uncertainty Areas. ⋮ Scheduling with a processing time oracle ⋮ Explorable uncertainty in scheduling with non-uniform testing times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The update complexity of selection and related problems
• The robust knapsack problem with queries
• Query-competitive algorithms for cheapest set problems under uncertainty
• Minimum Spanning Tree Verification Under Uncertainty
• Computing shortest paths with uncertainty
• Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Introduction to Stochastic Programming
• Computing the Median with Uncertainty
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Randomization Helps Computing a Minimum Spanning Tree under Uncertainty