Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Computer Science Research Works
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Computer Science Research Works
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    LP Randomized Rounding for Maximum Coverage Problem and Minimum Set Cover with Threshold Problem

    Thumbnail
    View/Open
    dual.ps (165.5Kb)
    No. of downloads: 348

    Auto-generated copy of dual.ps (172.7Kb)
    No. of downloads: 421

    Date
    2005-10-06
    Author
    Khuller, Samir
    Raschid, Louiqa
    Wu, Yao
    Metadata
    Show full item record
    Abstract
    There are abundance of web accessible life science sources. Traversal of a particular path can answer a navigational query, returning a target object set (TOS). The cardinality of TOS is considered as the benefit of a path and there is some cost function associated with each path. It is common that multiple alternate paths satisfy the query and we are not allowed to pick all these paths to answer the query, since there could be exponential number of paths in a graph. We are interested in selecting a subset of these paths. We present two problems in this context. The first problem is to select a subset of paths of maximum benefit within a cost budget. This is known as {\em Budgeted Maximum Coverage Problem} in the literature. The second problem is to select a subset of paths of minimum cost with a threshold benefit guarantee. This is the {\em Minimum Set Cover with Threshold Problem}. We develop randomized approximation algorithms based on LP rounding and conduct experiments.
    URI
    http://hdl.handle.net/1903/2814
    Collections
    • Computer Science Research Works

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility