• 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

Complexity of determining the most vital elements for the 1-median and 1-center location problems

Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2010), Complexity of determining the most vital elements for the 1-median and 1-center location problems, in Wu, Weili, Combinatorial Optimization and Combinatorial Optimization and Applications4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I, Springer : Berlin Heidelberg, p. 237-251. http://dx.doi.org/10.1007/978-3-642-17458-2_20

View/Open
complexity_vanderpooten.PDF (194.3Kb)
Type
Communication / Conférence
Date
2010
Conference country
UNITED STATES
Book title
Combinatorial Optimization and Combinatorial Optimization and Applications4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I
Book author
Wu, Weili
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-17457-5
Pages
237-251
Publication identifier
http://dx.doi.org/10.1007/978-3-642-17458-2_20
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Toubaline, Sónia
Vanderpooten, Daniel
Abstract (EN)
We consider the k most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) 1-median (respectively 1-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the 1-median (respectively 1-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker 1-median (respectively 1-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the 1-median (respectively 1-center) problem has a total weighted distance spectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges 1-median and k most vital edges 1-center are NP-hard to approximate within a factor 7 − and 4 − respectively, for any > 0, while k most 5 3 vital nodes 1-median and k most vital nodes 1-center are NP-hard to approximate within a factor 3 − , for any > 0. We also show that the 2 complementary versions of these four problems are NP-hard to approx imate within a factor 1.36.
Subjects / Keywords
1-median; 1-center; complexity; most vital edges and nodes; approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity of determining the most vital elements for the p-median and p-center location problems 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Efficient determination of the k most vital edges for the minimum spanning tree problem 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2012) Article accepté pour publication ou publié
  • Thumbnail
    Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011) Communication / Conférence
  • Thumbnail
    Critical edges for the assignment problem : complexity and exact resolution 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Critical edges/nodes for the minimum spanning tree problem: complexity and approximation 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) 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