Algorithmic expedients for the prize collecting Steiner tree problem

DOI10.1016/j.disopt.2010.01.001zbMath1271.90097OpenAlexW2087987937MaRDI QIDQ1952504

Mohamed Haouari, Safa Bhar Layeb, Hanif D. Sherali

Publication date: 31 May 2013

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.01.001

zbMATH Keywords

valid inequalitiesworst-case analysisSteiner treereduction techniques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)

Related Items

Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree, Exact approaches for solving robust prize-collecting Steiner tree problems

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Conjugate gradient methods using quasi-Newton updates with inexact line searches
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• Facets of two Steiner arborescence polyhedra
• Strong lower bounds for the prize collecting Steiner problem in graphs
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• The shortest route problem with constraints
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• The NP-completeness column: an ongoing guide
• Some generalizations of the steiner problem in graphs
• The node-weighted steiner tree problem
• An SST-based algorithm for the steiner problem in graphs
• The prize collecting traveling salesman problem
• An Efficient Primal Simplex Algorithm for Maximum Weighted Vertex Packing on Bipartite Graphs
• Algorithms - ESA 2003
• A comparison of Steiner tree relaxations