• 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

An improved general procedure for lexicographic bottleneck problems

Della Croce, Federico; Paschos, Vangelis; Tsoukiàs, Alexis (1999), An improved general procedure for lexicographic bottleneck problems, Operations Research Letters, 24, 4, p. 187-194. http://dx.doi.org/10.1016/S0167-6377(99)00013-9

View/Open
bottlene.pdf (211.9Kb)
Type
Article accepté pour publication ou publié
Date
1999
Journal name
Operations Research Letters
Volume
24
Number
4
Publisher
Elsevier
Pages
187-194
Publication identifier
http://dx.doi.org/10.1016/S0167-6377(99)00013-9
Metadata
Show full item record
Author(s)
Della Croce, Federico
Paschos, Vangelis
Tsoukiàs, Alexis cc
Abstract (EN)
In combinatorial optimization, the bottleneck (or minmax) problems are those problems where the objective is to find a feasible solution such that its largest cost coefficient elements have minimum cost. Here we consider a generalization of these problems, where under a lexicographic rule we want to minimize the cost also of the second largest cost coefficient elements, then of the third largest cost coefficients, and so on. We propose a general rule which leads, given the considered problem, to a vectorial version of the solution procedure for the underlying sum optimization (minsum) problem. This vectorial procedure increases by a factor of k (where k is the number of different cost coefficients) the complexity of the corresponding sum optimization problem solution procedure.
Subjects / Keywords
Combinatorial optimization; Bottleneck problem; Lexicographic problem

Related items

Showing items related by title and author.

  • 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
    Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems 
    Paschos, Vangelis; Della Croce, Federico (2008) Article accepté pour publication ou publié
  • Thumbnail
    An exact algorithm for MAX CUT in sparse graphs 
    Kaminski, Marcin; Della Croce, Federico; Paschos, Vangelis (2007) Article accepté pour publication ou publié
  • 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) Article accepté pour publication ou publié
  • Thumbnail
    Algorithms for dominating clique problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
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