Better Approximations for the Minimum Common Integer Partition Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

David P. Woodruff

ABSTRACT

In the k-Minimum Common Integer Partition Problem, abbreviated k-MCIP, we are given k multisets X1, ..., Xk of positive integers, and the goal is to find an integer multiset T of minimal size for which for each i, we can partition each of the integers in Xi so that the disjoint union (multiset union) of their partitions equals T. This problem has many applications to computational molecular biology, including ortholog assignment and fingerprint assembly.We prove better approximation ratios for k-MCIP by looking at what we call the redundancy of X1, ..., Xk, which is a quantity capturing the frequency of integers across the different Xi. Namely, we show .614k-approximability, improving upon the previous best known (k – 1/3)-approximability for this problem. A key feature of our algorithm is that it can be implemented in almost linear time. More... »

PAGES

248-259

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-38044-3
978-3-540-38045-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11830924_24

DOI

http://dx.doi.org/10.1007/11830924_24

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tsinghua University", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "MIT", 
            "Tsinghua University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "In the k-Minimum Common Integer Partition Problem, abbreviated k-MCIP, we are given k multisets X1, ..., Xk of positive integers, and the goal is to find an integer multiset T of minimal size for which for each i, we can partition each of the integers in Xi so that the disjoint union (multiset union) of their partitions equals T. This problem has many applications to computational molecular biology, including ortholog assignment and fingerprint assembly.We prove better approximation ratios for k-MCIP by looking at what we call the redundancy of X1, ..., Xk, which is a quantity capturing the frequency of integers across the different Xi. Namely, we show .614k-approximability, improving upon the previous best known (k \u2013 1/3)-approximability for this problem. A key feature of our algorithm is that it can be implemented in almost linear time.", 
    "editor": [
      {
        "familyName": "D\u00edaz", 
        "givenName": "Josep", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Zwick", 
        "givenName": "Uri", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11830924_24", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-38044-3", 
        "978-3-540-38045-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "integer partition problem", 
      "partition problem", 
      "minimum common integer partition problem", 
      "computational molecular biology", 
      "best approximation ratio", 
      "approximation ratio", 
      "linear time", 
      "ortholog assignment", 
      "key features", 
      "algorithm", 
      "redundancy", 
      "minimal size", 
      "approximability", 
      "integers", 
      "partition", 
      "good approximation", 
      "applications", 
      "features", 
      "goal", 
      "disjoint union", 
      "assignment", 
      "time", 
      "molecular biology", 
      "approximation", 
      "positive integer", 
      "size", 
      "quantity", 
      "Union", 
      "biology", 
      "assembly", 
      "X1", 
      "xk", 
      "ratio", 
      "frequency", 
      "XI", 
      "problem"
    ], 
    "name": "Better Approximations for the Minimum Common Integer Partition Problem", 
    "pagination": "248-259", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025014016"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11830924_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11830924_24", 
      "https://app.dimensions.ai/details/publication/pub.1025014016"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:55", 
    "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_58.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11830924_24"
  }
]
 

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/11830924_24'

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/11830924_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11830924_24'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11830924_24'


 

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

111 TRIPLES      22 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11830924_24 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N71375f3ca97848b6829bd0c2e77df870
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description In the k-Minimum Common Integer Partition Problem, abbreviated k-MCIP, we are given k multisets X1, ..., Xk of positive integers, and the goal is to find an integer multiset T of minimal size for which for each i, we can partition each of the integers in Xi so that the disjoint union (multiset union) of their partitions equals T. This problem has many applications to computational molecular biology, including ortholog assignment and fingerprint assembly.We prove better approximation ratios for k-MCIP by looking at what we call the redundancy of X1, ..., Xk, which is a quantity capturing the frequency of integers across the different Xi. Namely, we show .614k-approximability, improving upon the previous best known (k – 1/3)-approximability for this problem. A key feature of our algorithm is that it can be implemented in almost linear time.
7 schema:editor N0626347a1123454ba08cf654a2c09895
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ne70a91041ce943f6b880b6041957b842
11 schema:keywords Union
12 X1
13 XI
14 algorithm
15 applications
16 approximability
17 approximation
18 approximation ratio
19 assembly
20 assignment
21 best approximation ratio
22 biology
23 computational molecular biology
24 disjoint union
25 features
26 frequency
27 goal
28 good approximation
29 integer partition problem
30 integers
31 key features
32 linear time
33 minimal size
34 minimum common integer partition problem
35 molecular biology
36 ortholog assignment
37 partition
38 partition problem
39 positive integer
40 problem
41 quantity
42 ratio
43 redundancy
44 size
45 time
46 xk
47 schema:name Better Approximations for the Minimum Common Integer Partition Problem
48 schema:pagination 248-259
49 schema:productId N6ba188be8e7c47d1b46008bfde20ad05
50 N78c1d29f6e4445b1b80d7a0bf84ef556
51 schema:publisher Neb03254816414662ac708fa5f1c43311
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025014016
53 https://doi.org/10.1007/11830924_24
54 schema:sdDatePublished 2022-12-01T06:55
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N4927445c8cd74c18a0f95c75e6b2c214
57 schema:url https://doi.org/10.1007/11830924_24
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N0626347a1123454ba08cf654a2c09895 rdf:first N9a3abbe47f2e4d829c7a8075c707085f
62 rdf:rest N9519166e0e2f499ba496dcaf80005e53
63 N3e6e11c29fe845b6bb70734660c31071 schema:familyName Jansen
64 schema:givenName Klaus
65 rdf:type schema:Person
66 N4927445c8cd74c18a0f95c75e6b2c214 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N6ba188be8e7c47d1b46008bfde20ad05 schema:name doi
69 schema:value 10.1007/11830924_24
70 rdf:type schema:PropertyValue
71 N6d3d6c4dec40458683407ed4e9dfe177 rdf:first Naa32e3012a874649a0a2c3b307188064
72 rdf:rest Nd2be291be1c24ef18197d4c046328b50
73 N71375f3ca97848b6829bd0c2e77df870 rdf:first sg:person.012727410605.86
74 rdf:rest rdf:nil
75 N78c1d29f6e4445b1b80d7a0bf84ef556 schema:name dimensions_id
76 schema:value pub.1025014016
77 rdf:type schema:PropertyValue
78 N9519166e0e2f499ba496dcaf80005e53 rdf:first N3e6e11c29fe845b6bb70734660c31071
79 rdf:rest N6d3d6c4dec40458683407ed4e9dfe177
80 N9a3abbe47f2e4d829c7a8075c707085f schema:familyName Díaz
81 schema:givenName Josep
82 rdf:type schema:Person
83 Naa32e3012a874649a0a2c3b307188064 schema:familyName Rolim
84 schema:givenName José D. P.
85 rdf:type schema:Person
86 Nd2be291be1c24ef18197d4c046328b50 rdf:first Nfec6cf6f23c24c24a0435a2903a42fea
87 rdf:rest rdf:nil
88 Ne70a91041ce943f6b880b6041957b842 schema:isbn 978-3-540-38044-3
89 978-3-540-38045-0
90 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
91 rdf:type schema:Book
92 Neb03254816414662ac708fa5f1c43311 schema:name Springer Nature
93 rdf:type schema:Organisation
94 Nfec6cf6f23c24c24a0435a2903a42fea schema:familyName Zwick
95 schema:givenName Uri
96 rdf:type schema:Person
97 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
98 schema:name Mathematical Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Numerical and Computational Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.12527.33
104 schema:familyName Woodruff
105 schema:givenName David P.
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
107 rdf:type schema:Person
108 grid-institutes:grid.12527.33 schema:alternateName Tsinghua University
109 schema:name MIT
110 Tsinghua University
111 rdf:type schema:Organization
 




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


...