Variable Length Sequencing with Two Lengths View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Piotr Berman , Junichiro Fukuyama

ABSTRACT

Certain tasks, like accessing pages on the World Wide Web, require duration that varies over time. This poses the following Variable Length Sequencing Problem, or VLSP-L. Let [i, j) denote i, i+1, ..., j- 1. The problem is given by a set of jobs J and the time-dependent length function λ : J × [0, n) → L. A sequencing function σ : J →[0, n) assigns to each job j a time interval τσ(j) when this job is executed; if σ(j) = t then τσ(j) = [t, t+λ(j, t)). The sequencing is valid if these time intervals are disjoint. Our objective is to minimize the makespan, i. e. the maximum ending of an assign time interval. Recently it was shown VLSP-[0, n) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, k} an 2 - 1/k approximation was shown. This paper shows that for k ≥ 3 VLSP-{1, k} is MAX-SNP hard, and that we can approximate it with ratio 2 - 4/(k + 3). More... »

PAGES

51-59

Book

TITLE

Approximation Algorithms for Combinatorial Optimization

ISBN

978-3-540-67996-7
978-3-540-44436-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44436-x_7

DOI

http://dx.doi.org/10.1007/3-540-44436-x_7

DIMENSIONS

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


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/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 and Engineering, The Pennsylvania State University, Pennsylvania", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, Pennsylvania"
          ], 
          "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 and Engineering, The Pennsylvania State University, Pennsylvania", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, Pennsylvania"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fukuyama", 
        "givenName": "Junichiro", 
        "id": "sg:person.015266205731.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015266205731.31"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "Certain tasks, like accessing pages on the World Wide Web, require duration that varies over time. This poses the following Variable Length Sequencing Problem, or VLSP-L. Let [i, j) denote i, i+1, ..., j- 1. The problem is given by a set of jobs J and the time-dependent length function \u03bb : J \u00d7 [0, n) \u2192 L. A sequencing function \u03c3 : J \u2192[0, n) assigns to each job j a time interval \u03c4\u03c3(j) when this job is executed; if \u03c3(j) = t then \u03c4\u03c3(j) = [t, t+\u03bb(j, t)). The sequencing is valid if these time intervals are disjoint. Our objective is to minimize the makespan, i. e. the maximum ending of an assign time interval. Recently it was shown VLSP-[0, n) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, k} an 2 - 1/k approximation was shown. This paper shows that for k \u2265 3 VLSP-{1, k} is MAX-SNP hard, and that we can approximate it with ratio 2 - 4/(k + 3).", 
    "editor": [
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Khuller", 
        "givenName": "Samir", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44436-x_7", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67996-7", 
        "978-3-540-44436-7"
      ], 
      "name": "Approximation Algorithms for Combinatorial Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "time interval", 
      "interval", 
      "sequencing", 
      "duration", 
      "VLSP", 
      "endings", 
      "cases", 
      "objective", 
      "Web", 
      "time", 
      "length", 
      "certain tasks", 
      "World Wide Web", 
      "job j", 
      "MAX-SNP hard", 
      "Hard", 
      "task", 
      "Wide Web", 
      "problem", 
      "sequencing problem", 
      "ratio 2", 
      "jobs", 
      "makespan", 
      "NPs", 
      "pages", 
      "set", 
      "disjoint", 
      "general case", 
      "function \u03c3", 
      "approximation", 
      "paper", 
      "function \u03bb"
    ], 
    "name": "Variable Length Sequencing with Two Lengths", 
    "pagination": "51-59", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043301558"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44436-x_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44436-x_7", 
      "https://app.dimensions.ai/details/publication/pub.1043301558"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_162.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44436-x_7"
  }
]
 

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/3-540-44436-x_7'

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/3-540-44436-x_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_7'


 

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

103 TRIPLES      22 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44436-x_7 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N4b4e3d58cbe2474a8676e4d049dbae1b
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description Certain tasks, like accessing pages on the World Wide Web, require duration that varies over time. This poses the following Variable Length Sequencing Problem, or VLSP-L. Let [i, j) denote i, i+1, ..., j- 1. The problem is given by a set of jobs J and the time-dependent length function λ : J × [0, n) → L. A sequencing function σ : J →[0, n) assigns to each job j a time interval τσ(j) when this job is executed; if σ(j) = t then τσ(j) = [t, t+λ(j, t)). The sequencing is valid if these time intervals are disjoint. Our objective is to minimize the makespan, i. e. the maximum ending of an assign time interval. Recently it was shown VLSP-[0, n) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, k} an 2 - 1/k approximation was shown. This paper shows that for k ≥ 3 VLSP-{1, k} is MAX-SNP hard, and that we can approximate it with ratio 2 - 4/(k + 3).
7 schema:editor Na48a0a4737f0482e94ad77573d6a5891
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nacc27a4ae6094b728daffa24e9212629
11 schema:keywords Hard
12 MAX-SNP hard
13 NPs
14 VLSP
15 Web
16 Wide Web
17 World Wide Web
18 approximation
19 cases
20 certain tasks
21 disjoint
22 duration
23 endings
24 function λ
25 function σ
26 general case
27 interval
28 job j
29 jobs
30 length
31 makespan
32 objective
33 pages
34 paper
35 problem
36 ratio 2
37 sequencing
38 sequencing problem
39 set
40 task
41 time
42 time interval
43 schema:name Variable Length Sequencing with Two Lengths
44 schema:pagination 51-59
45 schema:productId Nad5b4f4261aa4e6c9e72993fb1793817
46 Naf7572a3bc5941b78fe572b7a8924777
47 schema:publisher N521692ad6993405e971dfd5b59c1a90c
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043301558
49 https://doi.org/10.1007/3-540-44436-x_7
50 schema:sdDatePublished 2022-08-04T17:15
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher Ne1144c3c0ac5488b8a7b0ec6e52eac13
53 schema:url https://doi.org/10.1007/3-540-44436-x_7
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N054db25a60914da19c695d1d12710b75 rdf:first sg:person.015266205731.31
58 rdf:rest rdf:nil
59 N22cac5a7478848d6a4bd76a8d2110dd2 schema:familyName Jansen
60 schema:givenName Klaus
61 rdf:type schema:Person
62 N4b4e3d58cbe2474a8676e4d049dbae1b rdf:first sg:person.01274506210.27
63 rdf:rest N054db25a60914da19c695d1d12710b75
64 N521692ad6993405e971dfd5b59c1a90c schema:name Springer Nature
65 rdf:type schema:Organisation
66 N7a3711353c7849bb8d39d54ae686e568 schema:familyName Khuller
67 schema:givenName Samir
68 rdf:type schema:Person
69 Na48a0a4737f0482e94ad77573d6a5891 rdf:first N22cac5a7478848d6a4bd76a8d2110dd2
70 rdf:rest Ncedcf4f445ab4aa589881f989ea8e738
71 Nacc27a4ae6094b728daffa24e9212629 schema:isbn 978-3-540-44436-7
72 978-3-540-67996-7
73 schema:name Approximation Algorithms for Combinatorial Optimization
74 rdf:type schema:Book
75 Nad5b4f4261aa4e6c9e72993fb1793817 schema:name dimensions_id
76 schema:value pub.1043301558
77 rdf:type schema:PropertyValue
78 Naf7572a3bc5941b78fe572b7a8924777 schema:name doi
79 schema:value 10.1007/3-540-44436-x_7
80 rdf:type schema:PropertyValue
81 Ncedcf4f445ab4aa589881f989ea8e738 rdf:first N7a3711353c7849bb8d39d54ae686e568
82 rdf:rest rdf:nil
83 Ne1144c3c0ac5488b8a7b0ec6e52eac13 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
89 schema:name Artificial Intelligence and Image Processing
90 rdf:type schema:DefinedTerm
91 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
92 schema:familyName Berman
93 schema:givenName Piotr
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
95 rdf:type schema:Person
96 sg:person.015266205731.31 schema:affiliation grid-institutes:grid.29857.31
97 schema:familyName Fukuyama
98 schema:givenName Junichiro
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015266205731.31
100 rdf:type schema:Person
101 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, The Pennsylvania State University, Pennsylvania
102 schema:name Department of Computer Science and Engineering, The Pennsylvania State University, Pennsylvania
103 rdf:type schema:Organization
 




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


...