# On Approximating a Scheduling Problem

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2001-09

AUTHORS 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
• ### Journal

TITLE

Journal of Combinatorial Optimization

ISSUE

3

VOLUME

5

### 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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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"
},
"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",
}
],
"keywords": [
"total time",
"completion",
"factors",
"cases",
"hand",
"ratio",
"time",
"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",
"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"
}
]

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'

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
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
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
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
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
67 schema:sdPublisher N6a3937f0c9e04868a23bff8ddcd9cc72
68 schema:url https://doi.org/10.1023/a:1011441109660
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
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
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
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