Prize-collecting steiner network problems

DOI10.1145/2390176.2390178MaRDI QIDQ2933630zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Mohammad T. Hajiaghayi, Guy Kortsarz, Zeev Nutov

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2390176.2390178

zbMATH Keywords

all-or-nothing flowsedge-connectivityprize-collectingSteiner Network problemvertex-connectivity

Mathematics Subject Classification ID

Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Prize-collecting Steiner network problems
• scientific article; zbMATH DE number 6783450
• Prize-collecting Steiner networks via iterative rounding
• scientific article; zbMATH DE number 1445375
• On the Exact Solution of Prize-Collecting Steiner Tree Problems
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Generating lower bounds for the prize collecting Steiner problem in graphs
• Variations of the prize‐collecting Steiner tree problem
• Algorithmic expedients for the prize collecting Steiner tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem

Cited in

(5)

• Prize-collecting survivable network design in node-weighted graphs
• Prize-collecting Steiner network problems
• Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• 2-approximation for prize-collecting Steiner forest

This page was built for publication: Prize-collecting steiner network problems

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