On Approximating an Implicit Cover Problem in Biology View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Mary V. Ashley , Tanya Y. Berger-Wolf , Wanpracha Chaovalitwongse , Bhaskar DasGupta , Ashfaq Khokhar , Saad Sheikh

ABSTRACT

In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly. For example, the well-known minimum feedback arc set problem is such a problem. In this paper, we consider such a cover problem that arises in the study of wild populations in biology in which the sets are defined implicitly via the Mendelian constraints and prove approximability results for this problem. More... »

PAGES

43-54

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02158-9_6

DOI

http://dx.doi.org/10.1007/978-3-642-02158-9_6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1004010445


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Biological Sciences, University of Illinois at Chicago, 840 West Taylor Street, IL 60607, Chicago, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Biological Sciences, University of Illinois at Chicago, 840 West Taylor Street, IL 60607, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ashley", 
        "givenName": "Mary V.", 
        "id": "sg:person.01211361043.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01211361043.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berger-Wolf", 
        "givenName": "Tanya Y.", 
        "id": "sg:person.010146520437.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010146520437.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Industrial Engineering, Rutgers University, PO Box 909, NJ 08855, Piscataway, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Industrial Engineering, Rutgers University, PO Box 909, NJ 08855, Piscataway, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chaovalitwongse", 
        "givenName": "Wanpracha", 
        "id": "sg:person.01325607443.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01325607443.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Khokhar", 
        "givenName": "Ashfaq", 
        "id": "sg:person.07702130430.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07702130430.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sheikh", 
        "givenName": "Saad", 
        "id": "sg:person.01075132443.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01075132443.65"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly. For example, the well-known minimum feedback arc set problem is such a problem. In this paper, we consider such a cover problem that arises in the study of wild populations in biology in which the sets are defined implicitly via the Mendelian constraints and prove approximability results for this problem.", 
    "editor": [
      {
        "familyName": "Goldberg", 
        "givenName": "Andrew V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhou", 
        "givenName": "Yunhong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02158-9_6", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02157-2", 
        "978-3-642-02158-9"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "cover problem", 
      "minimum feedback arc set problem", 
      "combinatorial optimization problems", 
      "feedback arc set problem", 
      "set cover problem", 
      "optimization problem", 
      "auxiliary algorithm", 
      "approximability results", 
      "set problem", 
      "Mendelian constraints", 
      "important subclass", 
      "such problems", 
      "problem", 
      "constraints", 
      "equations", 
      "set", 
      "algorithm", 
      "subclasses", 
      "example", 
      "results", 
      "biology", 
      "study", 
      "population", 
      "wild populations", 
      "paper"
    ], 
    "name": "On Approximating an Implicit Cover Problem in Biology", 
    "pagination": "43-54", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004010445"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02158-9_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02158-9_6", 
      "https://app.dimensions.ai/details/publication/pub.1004010445"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_374.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-02158-9_6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02158-9_6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02158-9_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02158-9_6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02158-9_6'


 

This table displays all metadata directly associated to this object as RDF triples.

129 TRIPLES      22 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02158-9_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4ca4a7ca7203404db6198336b3d197cb
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly. For example, the well-known minimum feedback arc set problem is such a problem. In this paper, we consider such a cover problem that arises in the study of wild populations in biology in which the sets are defined implicitly via the Mendelian constraints and prove approximability results for this problem.
7 schema:editor Ne31cfddf3d6043bfb17e613541f66042
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N9b342f560c124e3aab9a859737ada823
11 schema:keywords Mendelian constraints
12 algorithm
13 approximability results
14 auxiliary algorithm
15 biology
16 combinatorial optimization problems
17 constraints
18 cover problem
19 equations
20 example
21 feedback arc set problem
22 important subclass
23 minimum feedback arc set problem
24 optimization problem
25 paper
26 population
27 problem
28 results
29 set
30 set cover problem
31 set problem
32 study
33 subclasses
34 such problems
35 wild populations
36 schema:name On Approximating an Implicit Cover Problem in Biology
37 schema:pagination 43-54
38 schema:productId N754d70de634a4c8d8bdf3c6caac6f987
39 N8ac87bec6989494fb6fa1c7fa1b93e1e
40 schema:publisher N852281bbdfb0412cb5495a1f669a6c9b
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004010445
42 https://doi.org/10.1007/978-3-642-02158-9_6
43 schema:sdDatePublished 2022-12-01T06:52
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N133af3489e0e4019beb50539b6bf94bd
46 schema:url https://doi.org/10.1007/978-3-642-02158-9_6
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N045c82f7514e4895826561287cc27992 rdf:first sg:person.07702130430.62
51 rdf:rest N55d1703fefde4be5b287f9f250254504
52 N133af3489e0e4019beb50539b6bf94bd schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N29df3c2122184e22a5aae2bf19d5ad3f rdf:first sg:person.0763403270.10
55 rdf:rest N045c82f7514e4895826561287cc27992
56 N43230861bbe04fcb95a3c88a83b06f8d rdf:first sg:person.01325607443.04
57 rdf:rest N29df3c2122184e22a5aae2bf19d5ad3f
58 N4ca4a7ca7203404db6198336b3d197cb rdf:first sg:person.01211361043.74
59 rdf:rest Nd3eeee10f2674672be6aa1ec5b87f18b
60 N50b5f0a6cc6240be831e188151275ebb schema:familyName Goldberg
61 schema:givenName Andrew V.
62 rdf:type schema:Person
63 N55d1703fefde4be5b287f9f250254504 rdf:first sg:person.01075132443.65
64 rdf:rest rdf:nil
65 N5e7a4a17e7af42e3a76d4b5b02dd1215 schema:familyName Zhou
66 schema:givenName Yunhong
67 rdf:type schema:Person
68 N754d70de634a4c8d8bdf3c6caac6f987 schema:name dimensions_id
69 schema:value pub.1004010445
70 rdf:type schema:PropertyValue
71 N852281bbdfb0412cb5495a1f669a6c9b schema:name Springer Nature
72 rdf:type schema:Organisation
73 N8ac87bec6989494fb6fa1c7fa1b93e1e schema:name doi
74 schema:value 10.1007/978-3-642-02158-9_6
75 rdf:type schema:PropertyValue
76 N9b342f560c124e3aab9a859737ada823 schema:isbn 978-3-642-02157-2
77 978-3-642-02158-9
78 schema:name Algorithmic Aspects in Information and Management
79 rdf:type schema:Book
80 Nd3eeee10f2674672be6aa1ec5b87f18b rdf:first sg:person.010146520437.19
81 rdf:rest N43230861bbe04fcb95a3c88a83b06f8d
82 Ne31cfddf3d6043bfb17e613541f66042 rdf:first N50b5f0a6cc6240be831e188151275ebb
83 rdf:rest Ne7466cde6cd048bcafa0ad69bbbe83cf
84 Ne7466cde6cd048bcafa0ad69bbbe83cf rdf:first N5e7a4a17e7af42e3a76d4b5b02dd1215
85 rdf:rest rdf:nil
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.010146520437.19 schema:affiliation grid-institutes:grid.185648.6
93 schema:familyName Berger-Wolf
94 schema:givenName Tanya Y.
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010146520437.19
96 rdf:type schema:Person
97 sg:person.01075132443.65 schema:affiliation grid-institutes:grid.185648.6
98 schema:familyName Sheikh
99 schema:givenName Saad
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01075132443.65
101 rdf:type schema:Person
102 sg:person.01211361043.74 schema:affiliation grid-institutes:grid.185648.6
103 schema:familyName Ashley
104 schema:givenName Mary V.
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01211361043.74
106 rdf:type schema:Person
107 sg:person.01325607443.04 schema:affiliation grid-institutes:grid.430387.b
108 schema:familyName Chaovalitwongse
109 schema:givenName Wanpracha
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01325607443.04
111 rdf:type schema:Person
112 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
113 schema:familyName DasGupta
114 schema:givenName Bhaskar
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
116 rdf:type schema:Person
117 sg:person.07702130430.62 schema:affiliation grid-institutes:grid.185648.6
118 schema:familyName Khokhar
119 schema:givenName Ashfaq
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07702130430.62
121 rdf:type schema:Person
122 grid-institutes:grid.185648.6 schema:alternateName Department of Biological Sciences, University of Illinois at Chicago, 840 West Taylor Street, IL 60607, Chicago, USA
123 Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA
124 schema:name Department of Biological Sciences, University of Illinois at Chicago, 840 West Taylor Street, IL 60607, Chicago, USA
125 Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street, IL 60607, Chicago, USA
126 rdf:type schema:Organization
127 grid-institutes:grid.430387.b schema:alternateName Department of Industrial Engineering, Rutgers University, PO Box 909, NJ 08855, Piscataway, USA
128 schema:name Department of Industrial Engineering, Rutgers University, PO Box 909, NJ 08855, Piscataway, USA
129 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...