Please use this identifier to cite or link to this item:
Title: Query-competitive algorithms for cheapest set problems under uncertainty
Authors: Erlebach, Thomas
Hoffmann, Michael
Kammer, F.
First Published: 2014
Presented at: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. In Proceedings, Part II
Publisher: Springer Verlag (Germany)
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8635 LNCS (PART 2), pp. 263-274
Abstract: 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.
Series/Report no.: Lecture Notes in Computer Science;8635
DOI Link: 10.1007/978-3-662-44465-8_23
ISSN: 0302-9743
ISBN: 978-3-662-44464-1
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
MFCS2014_FinalAuthorVersion.pdfPost-review (final submitted)266.07 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.