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

Simple item page
dc.contributor.authorKhuller, Samir
dc.contributor.authorRaschid, Louiqa
dc.contributor.authorWu, Yao
dc.date.accessioned2005-10-06T16:28:27Z
dc.date.available2005-10-06T16:28:27Z
dc.date.issued2005-10-06T16:28:27Z
dc.description.abstractThere 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.en
dc.format.extent169560 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/2814
dc.language.isoen_USen
dc.relation.isAvailableAtCollege of Computer, Methematical & Physical Sciencesen_us
dc.relation.isAvailableAtComputer Scienceen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_us
dc.subjectLPen
dc.subjectalgorithmsen
dc.titleLP Randomized Rounding for Maximum Coverage Problem and Minimum Set Cover with Threshold Problemen
dc.typeArticleen

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
dual.ps
Size:
165.59 KB
Format:
Postscript Files
Download
Thumbnail Image
Name:
dual.pdf
Size:
172.78 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of dual.ps
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.81 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Computer Science Research Works