On Approximating a Scheduling Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-09

AUTHORS

Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou

ABSTRACT

Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge's original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{7}{6}$$ \end{document} unless P=NP. It is known that a simple approximation algorithm achieves within a ratio of two (H. Choi and S.L. Hakimi, Algorithmica, vol. 3, pp. 223–245, 1988). However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm (I.S. Gopal and C.K. Wong, IEEE Transactions on Communications, vol. 33, pp. 497–501, 1985). We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance. Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances. More... »

PAGES

287-297

References to SciGraph publications

  • 1988-11. Data transfers in networks in ALGORITHMICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1011441109660

    DOI

    http://dx.doi.org/10.1023/a:1011441109660

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "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": "Dipartimento di Sistemi e Informatica, Universit\u00e0 degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy", 
              "id": "http://www.grid.ac/institutes/grid.8404.8", 
              "name": [
                "Dipartimento di Sistemi e Informatica, Universit\u00e0 degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Crescenzi", 
            "givenName": "Pierluigi", 
            "id": "sg:person.01173734710.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR, China", 
              "id": "http://www.grid.ac/institutes/grid.35030.35", 
              "name": [
                "Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deng", 
            "givenName": "Xiaotie", 
            "id": "sg:person.011445672445.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011445672445.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.47840.3f", 
              "name": [
                "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Papadimitriou", 
            "givenName": "Christos H.", 
            "id": "sg:person.013233165465.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01762116", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053484338", 
              "https://doi.org/10.1007/bf01762116"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001-09", 
        "datePublishedReg": "2001-09-01", 
        "description": "Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge's original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\frac{7}{6}$$\n\\end{document} unless P=NP. It is known that a simple approximation algorithm achieves within a ratio of two (H. Choi and S.L. Hakimi, Algorithmica, vol. 3, pp. 223\u2013245, 1988). However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm (I.S. Gopal and C.K. Wong, IEEE Transactions on Communications, vol. 33, pp. 497\u2013501, 1985). We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance. Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances.", 
        "genre": "article", 
        "id": "sg:pub.10.1023/a:1011441109660", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "5"
          }
        ], 
        "keywords": [
          "total time", 
          "completion", 
          "factors", 
          "cases", 
          "hand", 
          "ratio", 
          "time", 
          "task", 
          "communication tasks", 
          "results", 
          "derives", 
          "instances", 
          "problem", 
          "cost", 
          "performance", 
          "one", 
          "way", 
          "hierarchy of algorithms", 
          "simple one", 
          "NP", 
          "set", 
          "hierarchy", 
          "better performance", 
          "worst case", 
          "algorithm", 
          "sophisticated algorithms", 
          "paper", 
          "actual instances", 
          "function algorithm", 
          "provable approximation ratio", 
          "worst-case performance", 
          "simple approximation algorithm", 
          "heuristic algorithm", 
          "good experimental performance", 
          "approximation algorithm", 
          "approximation ratio", 
          "scheduling problem", 
          "preemption", 
          "experimental results", 
          "experimental performance", 
          "potential function algorithm", 
          "sophisticated algorithm derives", 
          "algorithm derives"
        ], 
        "name": "On Approximating a Scheduling Problem", 
        "pagination": "287-297", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024097601"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1011441109660"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1011441109660", 
          "https://app.dimensions.ai/details/publication/pub.1024097601"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:11", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_316.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1023/a:1011441109660"
      }
    ]
     

    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.1023/a:1011441109660'

    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.1023/a:1011441109660'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1011441109660'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1011441109660'


     

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

    133 TRIPLES      22 PREDICATES      72 URIs      61 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1011441109660 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N0b7a712041d747b4bd1e75e09238d04a
    6 schema:citation sg:pub.10.1007/bf01762116
    7 schema:datePublished 2001-09
    8 schema:datePublishedReg 2001-09-01
    9 schema:description Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge's original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{7}{6}$$ \end{document} unless P=NP. It is known that a simple approximation algorithm achieves within a ratio of two (H. Choi and S.L. Hakimi, Algorithmica, vol. 3, pp. 223–245, 1988). However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm (I.S. Gopal and C.K. Wong, IEEE Transactions on Communications, vol. 33, pp. 497–501, 1985). We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance. Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf Nb1c8aca1a5844f88b886c83ddf6932c7
    14 Nf7424bd0b7e34690a7e80adbf3b721ab
    15 sg:journal.1036683
    16 schema:keywords NP
    17 actual instances
    18 algorithm
    19 algorithm derives
    20 approximation algorithm
    21 approximation ratio
    22 better performance
    23 cases
    24 communication tasks
    25 completion
    26 cost
    27 derives
    28 experimental performance
    29 experimental results
    30 factors
    31 function algorithm
    32 good experimental performance
    33 hand
    34 heuristic algorithm
    35 hierarchy
    36 hierarchy of algorithms
    37 instances
    38 one
    39 paper
    40 performance
    41 potential function algorithm
    42 preemption
    43 problem
    44 provable approximation ratio
    45 ratio
    46 results
    47 scheduling problem
    48 set
    49 simple approximation algorithm
    50 simple one
    51 sophisticated algorithm derives
    52 sophisticated algorithms
    53 task
    54 time
    55 total time
    56 way
    57 worst case
    58 worst-case performance
    59 schema:name On Approximating a Scheduling Problem
    60 schema:pagination 287-297
    61 schema:productId N6a67e3f57c7b4404985882915e1f4c9c
    62 N7a9a7f755a3846f39b7a64ae545a7de6
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024097601
    64 https://doi.org/10.1023/a:1011441109660
    65 schema:sdDatePublished 2021-12-01T19:11
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher N6a3937f0c9e04868a23bff8ddcd9cc72
    68 schema:url https://doi.org/10.1023/a:1011441109660
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N0b7a712041d747b4bd1e75e09238d04a rdf:first sg:person.01173734710.11
    73 rdf:rest Nd7982302f6cc4813a9c259fd7551dde7
    74 N6a3937f0c9e04868a23bff8ddcd9cc72 schema:name Springer Nature - SN SciGraph project
    75 rdf:type schema:Organization
    76 N6a67e3f57c7b4404985882915e1f4c9c schema:name dimensions_id
    77 schema:value pub.1024097601
    78 rdf:type schema:PropertyValue
    79 N7a9a7f755a3846f39b7a64ae545a7de6 schema:name doi
    80 schema:value 10.1023/a:1011441109660
    81 rdf:type schema:PropertyValue
    82 Nb1c8aca1a5844f88b886c83ddf6932c7 schema:volumeNumber 5
    83 rdf:type schema:PublicationVolume
    84 Nb2a15a94e155451290343d99871372d5 rdf:first sg:person.013233165465.63
    85 rdf:rest rdf:nil
    86 Nd7982302f6cc4813a9c259fd7551dde7 rdf:first sg:person.011445672445.19
    87 rdf:rest Nb2a15a94e155451290343d99871372d5
    88 Nf7424bd0b7e34690a7e80adbf3b721ab schema:issueNumber 3
    89 rdf:type schema:PublicationIssue
    90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Mathematical Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Pure Mathematics
    95 rdf:type schema:DefinedTerm
    96 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Applied Mathematics
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Numerical and Computational Mathematics
    101 rdf:type schema:DefinedTerm
    102 sg:journal.1036683 schema:issn 1382-6905
    103 1573-2886
    104 schema:name Journal of Combinatorial Optimization
    105 schema:publisher Springer Nature
    106 rdf:type schema:Periodical
    107 sg:person.011445672445.19 schema:affiliation grid-institutes:grid.35030.35
    108 schema:familyName Deng
    109 schema:givenName Xiaotie
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011445672445.19
    111 rdf:type schema:Person
    112 sg:person.01173734710.11 schema:affiliation grid-institutes:grid.8404.8
    113 schema:familyName Crescenzi
    114 schema:givenName Pierluigi
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11
    116 rdf:type schema:Person
    117 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
    118 schema:familyName Papadimitriou
    119 schema:givenName Christos H.
    120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
    121 rdf:type schema:Person
    122 sg:pub.10.1007/bf01762116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053484338
    123 https://doi.org/10.1007/bf01762116
    124 rdf:type schema:CreativeWork
    125 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR, China
    126 schema:name Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR, China
    127 rdf:type schema:Organization
    128 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA
    129 schema:name Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA
    130 rdf:type schema:Organization
    131 grid-institutes:grid.8404.8 schema:alternateName Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy
    132 schema:name Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy
    133 rdf:type schema:Organization
     




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


    ...