• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem

Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004), Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem, Journal of Scheduling, 7, 1, p. 85-91. http://dx.doi.org/10.1023/B:JOSH.0000013056.09936.fd

View/Open
cahier193.pdf (391.3Kb)
Type
Article accepté pour publication ou publié
Date
2004
Journal name
Journal of Scheduling
Volume
7
Number
1
Publisher
Springer
Pages
85-91
Publication identifier
http://dx.doi.org/10.1023/B:JOSH.0000013056.09936.fd
Metadata
Show full item record
Author(s)
Grosso, Andrea
Della Croce, Federico
Paschos, Vangelis
Abstract (EN)
The weakly NP-hard single-machine total tardiness scheduling problem has been extensively studied in the last decades. Various heuristics have been proposed to efficiently solve in practice a problem for which a fully polynomial time approximation scheme exists (though with complexity O(n 7/E)). In this note, we show that all known constructive heuristics for the problem, namely AU, MDD, PSK, WI, COVERT, NBR, present arbitrarily bad approximation ratios. The same behavior is shown by the decomposition heuristics DEC/EDD, DEC/MDD, DEC/PSK, and DEC/WI.
Subjects / Keywords
Approximation; Scheduling; Total tardiness

Related items

Showing items related by title and author.

  • Thumbnail
    A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios 
    Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
  • Thumbnail
    Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 
    Baburin, Aleksei; Della Croce, Federico; Gimadi, Edward; Glazkov, Yuri; Paschos, Vangelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    The complexity of single machine scheduling problems under scenario-based uncertainty 
    Della Croce, Federico; Aloulou, Mohamed Ali (2008) Chapitre d'ouvrage
  • Thumbnail
    Improved worst-case complexity for the MIN 3-SET COVERING problem 
    Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007) Article accepté pour publication ou publié
  • Thumbnail
    Efficient Algorithms for the max k -vertex cover Problem 
    Della Croce, Federico; Paschos, Vangelis (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo