Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

Recommendations

Randomization helps computing a minimum spanning tree under uncertainty
On the value of a random minimum spanning tree problem
Computing minimum spanning trees with uncertainty
scientific article; zbMATH DE number 2119732
Randomized minimum spanning tree algorithms using exponentially fewer random bits
Minimum spanning tree under explorable uncertainty in theory and experiments
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
A randomly weighted minimum spanning tree with a random cost constraint
A randomly weighted minimum spanning tree with a random cost constraint
On finding a minimum spanning tree in a network with random weights

Cites work

Combinatorial optimization. Theory and algorithms.
Computing minimum spanning trees with uncertainty
Computing shortest paths with uncertainty
Computing the Median with Uncertainty
scientific article; zbMATH DE number 1232130 (Why is no real title available?)
scientific article; zbMATH DE number 7075885 (Why is no real title available?)
Introduction to Stochastic Programming
Minimum spanning tree verification under uncertainty
Query-competitive algorithms for cheapest set problems under uncertainty
Randomization helps computing a minimum spanning tree under uncertainty
Robust optimization
The robust knapsack problem with queries
The update complexity of selection and related problems
Two-sided online bipartite matching and vertex cover: beating the greedy algorithm

Cited in

(26)

Scheduling with a processing time oracle
Explorable uncertainty in scheduling with non-uniform testing times
Two-stage robust optimization problems with two-stage uncertainty
An adversarial model for scheduling with testing
Query-competitive sorting with uncertainty
Round-competitive algorithms for uncertainty problems with parallel queries
Query-competitive algorithms for cheapest set problems under uncertainty
Randomization helps computing a minimum spanning tree under uncertainty
Minimum spanning tree under explorable uncertainty in theory and experiments
Computing minimum spanning trees with uncertainty
The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
Query-Competitive Sorting with Uncertainty.
scientific article; zbMATH DE number 5658688 (Why is no real title available?)
Query minimization under stochastic uncertainty
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Set selection under explorable stochastic uncertainty via covering techniques
Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
The robust selection problem with information discovery
Competitive query minimization for stable matching with one-sided uncertainty
Learning-augmented query policies for minimum spanning tree with uncertainty
Round-competitive algorithms for uncertainty problems with parallel queries
On the complexity of knapsack under explorable uncertainty: hardness and algorithms
Identifying approximate minimizers under stochastic uncertainity
Algorithms that access the input via queries
Scheduling with testing on multiple identical parallel machines
Query-competitive algorithms for cheapest set problems under uncertainty

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283242)