Query-competitive algorithms for cheapest set problems under uncertainty

DOI10.1016/J.TCS.2015.11.025zbMATH Open1333.68300OpenAlexW2275305088MaRDI QIDQ899309FDOQ899309

N. E. Zubov

Publication date: 28 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.025

Recommendations

• Query-competitive algorithms for cheapest set problems under uncertainty
• Algorithms for queryable uncertainty
• Randomization helps computing a minimum spanning tree under uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• scientific article; zbMATH DE number 7075885

zbMATH Keywords

verificationonline algorithmscompetitive analysismatroidminimum multi-cut

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Fixed-parameter tractability and data reduction for multicut in trees
• Title not available (Why is that?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• The update complexity of selection and related problems
• Computing the Median with Uncertainty
• Title not available (Why is that?)
• Efficient update strategies for geometric computing with uncertainty
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A theorem on families of sets
• Computing shortest paths with uncertainty
• On minimum- and maximum-weight minimum spanning trees with neighborhoods
• Title not available (Why is that?)
• Verification Problem of Maximal Points under Uncertainty
• Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty
• Input-Thrifty Extrema Testing
• Largest and Smallest Tours and Convex Hulls for Imprecise Points

Cited In (15)

• Online makespan minimization with budgeted uncertainty
• Scheduling with a processing time oracle
• The power of amortization on scheduling with explorable uncertainty
• Query-Competitive Sorting with Uncertainty.
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• Algorithms for Queryable Uncertainty
• Set selection under explorable stochastic uncertainty via covering techniques
• A robust optimization approach with probe-able uncertainty
• Query-competitive sorting with uncertainty
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• Query minimization under stochastic uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Round-competitive algorithms for uncertainty problems with parallel queries
• Optimal path discovery problem with homogeneous knowledge
• Title not available (Why is that?)

This page was built for publication: Query-competitive algorithms for cheapest set problems under uncertainty

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