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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, Camden, 08102, NJ, 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, Rutgers University, Camden, 08102, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Palis", 
        "givenName": "Michael A.", 
        "id": "sg:person.014544155027.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014544155027.25"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretchf actor \u03b1 (or, equivalently, their maximum execution rate r = 1/\u03b1). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model in which a job must be completed if it was admitted for execution by the online scheduler, and the firm real-time scheduling model in which the scheduler is allowed not to complete a job even if it was admitted for execution by the online scheduler. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion, preemption is allowed, and the online scheduler must immediately decide, whenever a job arrives, whether to admit it for execution or reject it. We measure the competitive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/\u03b1)+\u03b5 for hard real-time scheduling with K \u2265 1 machines and greater than 1- (3/(4[\u03b1]) + \u03b5 for firm real-time scheduling on a single machine, where \u03b5 > 0 may be arbitrarily small, even if the algorithm is allowed to know the value of \u00e1 in advance. On the other hand, we exhibit a simple online scheduler that achieves a competitive ratio of at least 1-(1/\u03b1) in either of these models with K machines. The performance guarantee of our simple scheduler shows that it is in fact an optimal scheduler for hard real-time scheduling with K machines. We also describe an alternative scheduler for firm real-time scheduling on a single machine in which the competitive ratio does not go to zero as \u03b1 approaches 1. Both of our schedulers do not know the value of \u03b1 in advance.", 
    "editor": [
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Khuller", 
        "givenName": "Samir", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44436-x_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67996-7", 
        "978-3-540-44436-7"
      ], 
      "name": "Approximation Algorithms for Combinatorial Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "real-time scheduling model", 
      "online scheduler", 
      "online algorithm", 
      "hard real-time scheduling", 
      "scheduling model", 
      "real-time scheduling", 
      "competitive ratio", 
      "execution time", 
      "offline algorithm", 
      "performance guarantees", 
      "preemptive scheduling", 
      "scheduler", 
      "preemptive model", 
      "algorithm", 
      "execution", 
      "scheduling", 
      "objective function", 
      "machine", 
      "jobs", 
      "practical applications", 
      "deadlines", 
      "guarantees", 
      "preemption", 
      "model", 
      "applications", 
      "bounds", 
      "interest", 
      "terms", 
      "time", 
      "objective", 
      "sum", 
      "function", 
      "completion", 
      "ratio", 
      "values", 
      "paper"
    ], 
    "name": "Online Real-Time Preemptive Scheduling of Jobs with Deadlines", 
    "pagination": "96-107", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006803205"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44436-x_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44436-x_11", 
      "https://app.dimensions.ai/details/publication/pub.1006803205"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44436-x_11"
  }
]

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

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

108 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES