The update complexity of selection and related problems

DOI10.1007/S00224-015-9664-YMaRDI QIDQ315536zbMATHOpenAlexFDO

Authors Manoj Gupta, Yogish Sabharwal, Sandeep Sen

Publication date 21 September 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.5525

zbMATH Keywords

query complexitycompetitive ratiointerval datamodels of uncertainty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of data (68P99)

Abstract: We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in form of sub-intervals and the objective is to minimize the number of queries. The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.

Recommendations

• The update complexity of selection and related problems
• Computing the Median with Uncertainty
• Computing the median with uncertainty
• Round-competitive algorithms for uncertainty problems with parallel queries
• Computing minimum spanning trees with uncertainty

Cites work

• scientific article; zbMATH DE number 1962828 (Why is no real title available?)
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Computing minimum spanning trees with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Model-driven optimization using adaptive probes
• On the complexity of the robust spanning tree problem with interval data
• The update complexity of selection and related problems

Cited in

(12)

• Computing the Median with Uncertainty
• Query-competitive sorting with uncertainty
• Query-Competitive Sorting with Uncertainty.
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• Round-competitive algorithms for uncertainty problems with parallel queries
• The power of amortization on scheduling with explorable uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• The update complexity of selection and related problems
• An adversarial model for scheduling with testing
• Query minimization under stochastic uncertainty
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• scientific article; zbMATH DE number 3980537 (Why is no real title available?)

This page was built for publication: The update complexity of selection and related problems

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