• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Approximation results for the weighted P4 partition problems

Thumbnail
Date
2008
Dewey
Recherche opérationnelle
Sujet
Differential approximation; Standard approximation; Performance ratio; Approximation algorithms; P4-packing; Graph partitioning
Journal issue
Journal of discrete Algorithms
Volume
6
Number
2
Publication date
2008
Article pages
299-312
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.jda.2007.01.006
URI
https://basepub.dauphine.fr/handle/123456789/2105
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Toulouse, Sophie
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Abstract (EN)
We present several new standard and differential approximation results for the P4-partition problem using the Hassin and Rubinstein algorithm [Information Processing Letters 63 (1997) 63–67]. Those results concern both minimization and maximization versions of the problem. However, the main point of this paper lies in the establishment of the robustness of this algorithm, in the sense that it provides good quality solutions for a variety of versions of the problem, under both standard and differential approximation ratios.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.