Query-competitive algorithms for cheapest set problems under uncertainty

DOI10.1016/j.tcs.2015.11.025zbMath1333.68300OpenAlexW2275305088MaRDI QIDQ899309

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

zbMATH Keywords

verificationcompetitive analysisonline algorithmsmatroidminimum multi-cut

Mathematics Subject Classification ID

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

Related Items (13)

Online makespan minimization with budgeted 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 ⋮ Algorithms for Queryable Uncertainty ⋮ A robust optimization approach with probe-able uncertainty ⋮ Query minimization under stochastic uncertainty ⋮ Optimal path discovery problem with homogeneous knowledge ⋮ Query-Competitive Sorting with Uncertainty. ⋮ The Minimum Cost Query Problem on Matroids with Uncertainty Areas. ⋮ Randomization Helps Computing a Minimum Spanning Tree under Uncertainty ⋮ Scheduling with a processing time oracle

Cites Work

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

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