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

DOI10.1016/J.ORL.2003.11.002MaRDI QIDQ703233zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1445374 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• The SONET edge‐partition problem

Cited in

(9)

• Bicriteria approximation tradeoff for the node-cost budget problem
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Prize-collecting TSP with a budget constraint
• 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
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Approximation algorithms for constrained node weighted Steiner tree problems

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)