Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Faster approximation algorithms for scheduling with fixed jobs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2011 (English)In: Conferences in Research and Practice in Information Technology Series, 2011, 3-9 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study the problem of scheduling jobs on identical parallel machines without preemption. In the considered setting, some of the jobs are already assigned machines and starting times, for example due to external constraints not explicitly modelled. The objective is to assign the rest of the jobs in order to minimize the makespan. It is known that this problem cannot be approximated better than within a factor of 3/2 unless P = NP. An algorithm that achieves 3/2 + ε for any ε > 0 was presented by Diedrich and Jansen [DJ09], but its running time is doubly exponential in 1/ε. We present an improved algorithm with approximation ratio 3/2 and polynomial running time. We also give matching results for the related problem of scheduling with reservations. The new algorithm is both faster and conceptually simpler than the previously known algorithms.

Place, publisher, year, edition, pages
2011. 3-9 p.
Series
Conferences in Research and Practice in Information Technology Series, ISSN 1445-1336 ; 119
Keyword [en]
Approximation ratios, External constraints, Fixed jobs, Identical parallel machines, Makespan, Running time, Scheduling jobs, Approximation algorithms, Business machines, Polynomial approximation, Scheduling, Scheduling algorithms, Computation theory
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-149759Scopus ID: 2-s2.0-84864606866ISBN: 9781920682989 (print)OAI: oai:DiVA.org:kth-149759DiVA: diva2:749289
Conference
Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011, 17 January 2011 through 20 January 2011, Perth, WA
Note

QC 20140923

Available from: 2014-09-23 Created: 2014-08-27 Last updated: 2014-09-23Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Svensson, Ola
By organisation
Theoretical Computer Science, TCS
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf