Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries

Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima

The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of t…