On the edge capacitated Steiner tree problem

Autor: Marie-Christine Costa, Cédric Bentz, Alain Hertz
Přispěvatelé: CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Groupe d’études et de recherche en analyse des décisions (GERAD), Université du Québec à Montréal = University of Québec in Montréal (UQAM)-HEC Montréal (HEC Montréal)-McGill University = Université McGill [Montréal, Canada]-École Polytechnique de Montréal (EPM), PGMO project.
Jazyk: angličtina
Rok vydání: 2017
Předmět:
FOS: Computer and information sciences
vertex disjoint paths
Computational complexity theory
Discrete Mathematics (cs.DM)
Open problem
0211 other engineering and technologies
approximation
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Steiner tree problem
Theoretical Computer Science
Combinatorics
symbols.namesake
Steiner rooted tree
approximation algorithms
compelxity
Mathematics
computational complexity
021103 operations research
Graph optimization
Applied Mathematics
Steiner trees
Approximation algorithm
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Graph
capacity constraints
Open case
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Discrete Optimization
Discrete Optimization, Elsevier, 2020, 38, pp.100607. ⟨10.1016/j.disopt.2020.100607⟩
ISSN: 1572-5286
1873-636X
DOI: 10.1016/j.disopt.2020.100607⟩
Popis: Given a graph G = ( V , E ) with a root r ∈ V , positive capacities { c ( e ) | e ∈ E } , and non-negative lengths { l ( e ) | e ∈ E } , the minimum-length (rooted) edge capacitated Steiner tree problem is to find a tree in G of minimum total length, rooted at r , spanning a given subset T ⊂ V of vertices, and such that, for each e ∈ E , there are at most c ( e ) paths, linking r to vertices in T , that contain e . We study the complexity and approximability of the problem, considering several relevant parameters such as the number of terminals, the edge lengths and the minimum and maximum edge capacities. For all but one combinations of assumptions regarding these parameters, we settle the question, giving a complete characterization that separates tractable cases from hard ones. The only remaining open case is proved to be equivalent to a long-standing open problem. We also prove close relations between our problem and classic Steiner tree as well as vertex-disjoint paths problems.
Databáze: OpenAIRE
Externí odkaz: