Query-competitive algorithms for cheapest set problems under uncertainty
conference contributionposted on 2015-02-13, 10:03 authored by Thomas Erlebach, Michael Hoffmann, F. Kammer
Considering the model of computing under uncertainty where element weights are uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimum-weight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d·OPT+d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multi-cut problem in trees with d terminal pairs, we give an algorithm that makes at most d·OPT+1 queries. For the problem of computing a minimum-weight base of a given matroid, we give an algorithm that makes at most 2·OPT queries, generalizing a known result for the minimum spanning tree problem. For each of our algorithms we give matching lower bounds.
CitationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8635 LNCS (PART 2), pp. 263-274
Author affiliation/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science
Source39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. In Proceedings, Part II
- AM (Accepted Manuscript)