Approximation Algorithms in the Successive Hitting Set Model

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

STORANDT, Sabine, 2015. Approximation Algorithms in the Successive Hitting Set Model. 26th International Symposium, ISAAC 2015. Nagoya, Japan, Dec 9, 2015 - Dec 11, 2015. In: ELBASSIONI, Khaled, ed., Kazuhisa MAKINO, ed.. Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, proceedings. Heidelberg:Springer, pp. 453-464. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-662-48970-3. Available under: doi: 10.1007/978-3-662-48971-0_39

@inproceedings{Storandt2015-11-27Appro-43547, title={Approximation Algorithms in the Successive Hitting Set Model}, year={2015}, doi={10.1007/978-3-662-48971-0_39}, number={9472}, isbn={978-3-662-48970-3}, issn={0302-9743}, address={Heidelberg}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, proceedings}, pages={453--464}, editor={Elbassioni, Khaled and Makino, Kazuhisa}, author={Storandt, Sabine} }

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/43547"> <dcterms:abstract xml:lang="eng">We introduce the successive Hitting Set model, where the set system is not given in advance but a set generator produces the sets that contain a specific element from the universe on demand. Despite incomplete knowledge about the set system, we show that several approximation algorithms for the conventional Hitting Set problem can be adopted to perform well in this model. We describe, and experimentally investigate, several scenarios where the new model is beneficial compared to the conventional one.</dcterms:abstract> <dcterms:issued>2015-11-27</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-16T12:06:29Z</dc:date> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43547"/> <dc:contributor>Storandt, Sabine</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-16T12:06:29Z</dcterms:available> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Storandt, Sabine</dc:creator> <dc:language>eng</dc:language> <dcterms:title>Approximation Algorithms in the Successive Hitting Set Model</dcterms:title> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account