University of Leicester
Browse
MFCS2014_FinalAuthorVersion.pdf (266.07 kB)

Query-competitive algorithms for cheapest set problems under uncertainty

Download (266.07 kB)
conference contribution
posted 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.

History

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

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Source

39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. In Proceedings, Part II

Version

  • AM (Accepted Manuscript)

Published in

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Publisher

Springer Verlag (Germany)

issn

0302-9743

eissn

1611-3349

isbn

978-3-662-44464-1;978-3-662-44465-8

Copyright date

1007

Available date

2015-12-31

Publisher version

http://link.springer.com/chapter/10.1007/978-3-662-44465-8_23

Book series

Lecture Notes in Computer Science;8635

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC