Paper in TCS on computing with uncertainty

The paper "Query-competitive algorithms for cheapest set problems under uncertainty" by Erlebach and Hoffmann (co-authored with Kammer from University of Augsburg) has been published in Theoretical Computer Science in the February 2016 issue. The paper presents upper and lower bounds on the competitive ratio of algorithms that aim to minimize the number of queries required for finding the cheapest set among a collection of sets whose elements have uncertain costs.

DOI: 10.1016/j.tcs.2015.11.025

Filed under:

Share this page: