Risk models for the prize collecting Steiner tree problems with interval data

DOI10.1007/S10255-014-0269-ZzbMATH Open1373.68248OpenAlexW2033473042MaRDI QIDQ403434FDOQ403434

Authors: Alfredo Candia-Véjar, Xujin Chen, Bi Li, Eduardo Álvarez-Miranda, Xiaodong Hu 

Publication date: 29 August 2014

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-014-0269-z

Recommendations

• Probabilistic models for the Steiner tree problem
• Efficient algorithms for the prize collecting Steiner tree problems with interval data
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• scientific article; zbMATH DE number 1445375
• Exact approaches for solving robust prize-collecting Steiner tree problems
• Tight compact models and comparative analysis for the prize collecting Steiner tree problem
• The fractional prize-collecting Steiner tree problem on trees (extended abstract)
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• On the Exact Solution of Prize-Collecting Steiner Tree Problems
• A polynomial solvable minimum risk spanning tree problem with interval data

zbMATH Keywords

interval datauncertainty modelingpolynomial-time solvabilityprize collecting Steiner treeseries-parallel graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Strong lower bounds for the prize collecting Steiner problem in graphs
• The Steiner tree problem
• Interval data minmax regret network optimization problems
• Steiner trees, partial 2–trees, and minimum IFI networks
• Combinatorial Optimization with Rational Objective Functions
• A note on the prize collecting traveling salesman problem
• Title not available (Why is that?)
• On the complexity of the robust spanning tree problem with interval data
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• The computational complexity of the relative robust shortest path problem with interval data
• A polynomial solvable minimum risk spanning tree problem with interval data
• Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• Minimizing maximum risk for fair network connection with interval data
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• Earliest arrival flows on series-parallel graphs
• Efficient algorithms for the prize collecting Steiner tree problems with interval data
• Low-connectivity network design on series-parallel graphs
• Algorithms and Computation
• The computational complexity of the criticality problems in a network with interval activity times

Cited In (5)

• Min-max controllable risk problems
• Efficient algorithms for the prize collecting Steiner tree problems with interval data
• Robust optimization for routing problems on trees
• Min‐sum controllable risk problems with concave risk functions of the same value range
• Exact approaches for solving robust prize-collecting Steiner tree problems

This page was built for publication: Risk models for the prize collecting Steiner tree problems with interval data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403434)