Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Piotr Berman , Bhaskar DasGupta , Eduardo Sontag

ABSTRACT

In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial version of the problem and observe that this is “equivalent” to the set multicover problem when the “coverage” factor k is a function of the number of elements n of the universe. An important special case for our application is the case in which k=n–1.We observe that the standard greedy algorithm produces an approximation ratio of Ω(log n) even if k is “large” i.e.k=n–c for some constant c>0.Let 1 More... »

PAGES

39-50

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27821-4_4

DOI

http://dx.doi.org/10.1007/978-3-540-27821-4_4

DIMENSIONS

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


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 Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, 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 Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sontag", 
        "givenName": "Eduardo", 
        "id": "sg:person.0714217520.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: \nWe abstract a combinatorial version of the problem and observe that this is \u201cequivalent\u201d to the set multicover problem when the \u201ccoverage\u201d factor k is a function of the number of elements n of the universe. An important special case for our application is the case in which k=n\u20131.We observe that the standard greedy algorithm produces an approximation ratio of \u03a9(log n) even if k is \u201clarge\u201d i.e.k=n\u2013c for some constant c>0.Let 1
 

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-540-27821-4_4'

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-540-27821-4_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27821-4_4'

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-540-27821-4_4'


 

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

145 TRIPLES      23 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27821-4_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8178f3234bb54776bcf4583663aac026
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial version of the problem and observe that this is “equivalent” to the set multicover problem when the “coverage” factor k is a function of the number of elements n of the universe. An important special case for our application is the case in which k=n–1.We observe that the standard greedy algorithm produces an approximation ratio of Ω(log n) even if k is “large” i.e.k=n–c for some constant c>0.Let 1<a<n denotes the maximum number of elements in any given set in our set multicover problem. Then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio E[r(a,k)] that is an increasing function of a/k. The behavior of E[r(a,k)] is “roughly” as follows: it is about ln (a/k) when a/k is at least about e2≈ 7.39, and for smaller values of a/k it decreases towards 2 exponentially with increasing k with lima/ k→0E[r(a,k)]≤ 2. Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity β followed by a greedy solution for the remaining problem.
7 schema:editor N2b6fdc0ccc9542688ac40d43a4662f7e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N962804d3f0104b4295d0b20ad7ed6691
12 schema:keywords Ln
13 algorithm
14 analysis
15 applications
16 approximation algorithm
17 approximation ratio
18 behavior
19 cascade
20 cases
21 combinatorial problems
22 combinatorial version
23 complexity
24 computational complexity
25 contribution
26 coverage
27 deterministic
28 elements
29 elements N
30 engineering
31 engineering of proteins
32 expected approximation ratio
33 factor K
34 function
35 gene networks
36 greedy algorithm
37 greedy solution
38 important special case
39 maximum number
40 multicover problem
41 network
42 non-trivial analysis
43 number
44 paper
45 polynomial-time approximation algorithm
46 problem
47 protein
48 quantity β
49 randomized approximation algorithm
50 ratio
51 reverse engineering
52 set
53 set multicover problem
54 small values
55 solution
56 special case
57 standard greedy algorithm
58 step
59 universe
60 values
61 version
62 schema:name Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks
63 schema:pagination 39-50
64 schema:productId N1a17d818c701468390856fe1cd943a64
65 N28ae9f74d10e4c8395d69b3f0ac6e125
66 schema:publisher N4a310ee775784213ad9deab3d4c8e899
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052672908
68 https://doi.org/10.1007/978-3-540-27821-4_4
69 schema:sdDatePublished 2022-05-20T07:43
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N961269c7368049f69d003ac1c11326c7
72 schema:url https://doi.org/10.1007/978-3-540-27821-4_4
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N0290b79ec3ca4c2381c56997dfc4e7bd rdf:first N96447c2d3aa94efbb3c9d182205e8565
77 rdf:rest rdf:nil
78 N0f9917cde2dc485cacf1c03c4be6b31d rdf:first sg:person.0763403270.10
79 rdf:rest N3fc03a27c61946e4890deed487b3e2c1
80 N1809ad4bfa5a49aabaa178f476b2970c schema:familyName Khanna
81 schema:givenName Sanjeev
82 rdf:type schema:Person
83 N1a17d818c701468390856fe1cd943a64 schema:name dimensions_id
84 schema:value pub.1052672908
85 rdf:type schema:PropertyValue
86 N28ae9f74d10e4c8395d69b3f0ac6e125 schema:name doi
87 schema:value 10.1007/978-3-540-27821-4_4
88 rdf:type schema:PropertyValue
89 N2941135cb8774c0bac4d90e4ca8ea928 schema:familyName Rolim
90 schema:givenName José D. P.
91 rdf:type schema:Person
92 N2b6fdc0ccc9542688ac40d43a4662f7e rdf:first N5296e120abf9460ca11a4d6b6e534b5c
93 rdf:rest N98e500c08a9e446eb7f9dc5c7b208837
94 N3fc03a27c61946e4890deed487b3e2c1 rdf:first sg:person.0714217520.83
95 rdf:rest rdf:nil
96 N4a310ee775784213ad9deab3d4c8e899 schema:name Springer Nature
97 rdf:type schema:Organisation
98 N5296e120abf9460ca11a4d6b6e534b5c schema:familyName Jansen
99 schema:givenName Klaus
100 rdf:type schema:Person
101 N8178f3234bb54776bcf4583663aac026 rdf:first sg:person.01274506210.27
102 rdf:rest N0f9917cde2dc485cacf1c03c4be6b31d
103 N961269c7368049f69d003ac1c11326c7 schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 N962804d3f0104b4295d0b20ad7ed6691 schema:isbn 978-3-540-22894-3
106 978-3-540-27821-4
107 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
108 rdf:type schema:Book
109 N96447c2d3aa94efbb3c9d182205e8565 schema:familyName Ron
110 schema:givenName Dana
111 rdf:type schema:Person
112 N98e500c08a9e446eb7f9dc5c7b208837 rdf:first N1809ad4bfa5a49aabaa178f476b2970c
113 rdf:rest Nf2e4e6859d9f4705a321ea37be4afdee
114 Nf2e4e6859d9f4705a321ea37be4afdee rdf:first N2941135cb8774c0bac4d90e4ca8ea928
115 rdf:rest N0290b79ec3ca4c2381c56997dfc4e7bd
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
120 schema:name Computation Theory and Mathematics
121 rdf:type schema:DefinedTerm
122 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
123 schema:familyName Berman
124 schema:givenName Piotr
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
126 rdf:type schema:Person
127 sg:person.0714217520.83 schema:affiliation grid-institutes:grid.430387.b
128 schema:familyName Sontag
129 schema:givenName Eduardo
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83
131 rdf:type schema:Person
132 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
133 schema:familyName DasGupta
134 schema:givenName Bhaskar
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
136 rdf:type schema:Person
137 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
138 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
139 rdf:type schema:Organization
140 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
141 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
144 schema:name Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
145 rdf:type schema:Organization
 




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


...