Query-competitive algorithms for cheapest set problems under uncertainty

DOI10.1016/J.TCS.2015.11.025MaRDI QIDQ899309zbMATHOpenAlexFDO

Authors 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

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)

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

Cites work

• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• A theorem on families of sets
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Fixed-parameter tractability and data reduction for multicut in trees
• Input-Thrifty Extrema Testing
• Largest and Smallest Tours and Convex Hulls for Imprecise Points
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• On minimum- and maximum-weight minimum spanning trees with neighborhoods
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Query-competitive algorithms for cheapest set problems under uncertainty
• The update complexity of selection and related problems
• Verification problem of maximal points under uncertainty

Cited in

(16)

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

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)