Design Is as Easy as Optimization View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Deeparnab Chakrabarty , Aranyak Mehta , Vijay V. Vazirani

ABSTRACT

We identify a new genre of algorithmic problems – design problems – and study them from an algorithmic and complexity-theoretic view point. We use the learning techniques of Freund-Schapire [FS99] and its generalizations to show that for a large class of problems, the design version is as easy as the optimization version. More... »

PAGES

477-488

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-35904-3
978-3-540-35905-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11786986_42

DOI

http://dx.doi.org/10.1007/11786986_42

DIMENSIONS

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


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": "Georgia Institute of Technology, Atlanta, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "Georgia Institute of Technology, Atlanta, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chakrabarty", 
        "givenName": "Deeparnab", 
        "id": "sg:person.015353755525.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015353755525.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, San Jose, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, San Jose, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Georgia Institute of Technology, Atlanta, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "Georgia Institute of Technology, Atlanta, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vazirani", 
        "givenName": "Vijay V.", 
        "id": "sg:person.01023307450.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01023307450.97"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "We identify a new genre of algorithmic problems \u2013 design problems \u2013 and study them from an algorithmic and complexity-theoretic view point. We use the learning techniques of Freund-Schapire [FS99] and its generalizations to show that for a large class of problems, the design version is as easy as the optimization version.", 
    "editor": [
      {
        "familyName": "Bugliesi", 
        "givenName": "Michele", 
        "type": "Person"
      }, 
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }, 
      {
        "familyName": "Sassone", 
        "givenName": "Vladimiro", 
        "type": "Person"
      }, 
      {
        "familyName": "Wegener", 
        "givenName": "Ingo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11786986_42", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35904-3", 
        "978-3-540-35905-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "optimization version", 
      "large class", 
      "problem", 
      "generalization", 
      "optimization", 
      "view point", 
      "version", 
      "design versions", 
      "class", 
      "point", 
      "technique", 
      "design", 
      "new genre", 
      "genre"
    ], 
    "name": "Design Is as Easy as Optimization", 
    "pagination": "477-488", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009265057"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11786986_42"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11786986_42", 
      "https://app.dimensions.ai/details/publication/pub.1009265057"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:39", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_160.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11786986_42"
  }
]
 

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/11786986_42'

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/11786986_42'

Turtle is a human-readable linked data format.

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

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

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


 

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

106 TRIPLES      23 PREDICATES      40 URIs      33 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11786986_42 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N3283d506cb4b42528ee27e84b6d590f9
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description We identify a new genre of algorithmic problems – design problems – and study them from an algorithmic and complexity-theoretic view point. We use the learning techniques of Freund-Schapire [FS99] and its generalizations to show that for a large class of problems, the design version is as easy as the optimization version.
7 schema:editor N04458f0e5b16408aa0379a40f83d73e6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nbe154fffb4fb4240b483139a987fe038
12 schema:keywords class
13 design
14 design versions
15 generalization
16 genre
17 large class
18 new genre
19 optimization
20 optimization version
21 point
22 problem
23 technique
24 version
25 view point
26 schema:name Design Is as Easy as Optimization
27 schema:pagination 477-488
28 schema:productId Naaaf0a7b103b409d801507c28a644054
29 Ne966093d984345a5b7172a200edce748
30 schema:publisher N8bfd054ce8b142d18f02ab0a87d2058c
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009265057
32 https://doi.org/10.1007/11786986_42
33 schema:sdDatePublished 2022-05-10T10:39
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nf30cbe05755b4ebd8818b4bd73b426ad
36 schema:url https://doi.org/10.1007/11786986_42
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N02fc9f559d8a4522a7752d864ae9b370 schema:familyName Sassone
41 schema:givenName Vladimiro
42 rdf:type schema:Person
43 N04458f0e5b16408aa0379a40f83d73e6 rdf:first N3c2eac0c93d241048e1803f7e4962ea3
44 rdf:rest Nac88d168022c4109b4a1246cd085efae
45 N3283d506cb4b42528ee27e84b6d590f9 rdf:first sg:person.015353755525.91
46 rdf:rest Nb5a173784b624e1fb9dce2143ded1e6a
47 N3c2eac0c93d241048e1803f7e4962ea3 schema:familyName Bugliesi
48 schema:givenName Michele
49 rdf:type schema:Person
50 N6b3388925d0e4af29905e90f81cedb00 schema:familyName Wegener
51 schema:givenName Ingo
52 rdf:type schema:Person
53 N8bfd054ce8b142d18f02ab0a87d2058c schema:name Springer Nature
54 rdf:type schema:Organisation
55 N93691ea3bef547a999d88f7389f9d1be rdf:first sg:person.01023307450.97
56 rdf:rest rdf:nil
57 N97ae2ea0542c4c199d452c6ab74459b1 schema:familyName Preneel
58 schema:givenName Bart
59 rdf:type schema:Person
60 Naaaf0a7b103b409d801507c28a644054 schema:name dimensions_id
61 schema:value pub.1009265057
62 rdf:type schema:PropertyValue
63 Nac88d168022c4109b4a1246cd085efae rdf:first N97ae2ea0542c4c199d452c6ab74459b1
64 rdf:rest Nd24cd281a95745fb8972b4564a6893a0
65 Nb5a173784b624e1fb9dce2143ded1e6a rdf:first sg:person.010106546671.08
66 rdf:rest N93691ea3bef547a999d88f7389f9d1be
67 Nbe154fffb4fb4240b483139a987fe038 schema:isbn 978-3-540-35904-3
68 978-3-540-35905-0
69 schema:name Automata, Languages and Programming
70 rdf:type schema:Book
71 Nc2280cc253f744058129df74fa82edc9 rdf:first N6b3388925d0e4af29905e90f81cedb00
72 rdf:rest rdf:nil
73 Nd24cd281a95745fb8972b4564a6893a0 rdf:first N02fc9f559d8a4522a7752d864ae9b370
74 rdf:rest Nc2280cc253f744058129df74fa82edc9
75 Ne966093d984345a5b7172a200edce748 schema:name doi
76 schema:value 10.1007/11786986_42
77 rdf:type schema:PropertyValue
78 Nf30cbe05755b4ebd8818b4bd73b426ad schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
81 schema:name Mathematical Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
84 schema:name Numerical and Computational Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.481551.c
87 schema:familyName Mehta
88 schema:givenName Aranyak
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
90 rdf:type schema:Person
91 sg:person.01023307450.97 schema:affiliation grid-institutes:grid.213917.f
92 schema:familyName Vazirani
93 schema:givenName Vijay V.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01023307450.97
95 rdf:type schema:Person
96 sg:person.015353755525.91 schema:affiliation grid-institutes:grid.213917.f
97 schema:familyName Chakrabarty
98 schema:givenName Deeparnab
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015353755525.91
100 rdf:type schema:Person
101 grid-institutes:grid.213917.f schema:alternateName Georgia Institute of Technology, Atlanta, USA
102 schema:name Georgia Institute of Technology, Atlanta, USA
103 rdf:type schema:Organization
104 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, San Jose, USA
105 schema:name IBM Almaden Research Center, San Jose, USA
106 rdf:type schema:Organization
 




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


...