A better approximation algorithm for the budget prize collecting tree problem.

DOI10.1016/J.ORL.2003.11.002zbMATH Open1052.05065OpenAlexW1995327008MaRDI QIDQ703233FDOQ703233

Authors: Asaf Levin 

Publication date: 11 January 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2003.11.002

Recommendations

• scientific article; zbMATH DE number 1445375
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Prize-collecting TSP with a budget constraint
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems

zbMATH Keywords

subtreeApproximation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Approximation Schemes for the Restricted Shortest Path Problem
• A General Approximation Technique for Constrained Forest Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The SONET edge‐partition problem

Cited In (6)

• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
• An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
• Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Prize-Collecting TSP with a Budget Constraint

This page was built for publication: A better approximation algorithm for the budget prize collecting tree problem.

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