Improved approximation algorithms for prize-collecting Steiner tree and TSP

Recommendations

Elementary approximation algorithms for prize collecting Steiner tree problems
Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
scientific article; zbMATH DE number 1445375
scientific article; zbMATH DE number 6783450
Primal-dual approximation algorithms for the prize-collecting Steiner tree problem

Cited in

(44)

A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
The restricted Chinese postman problems with penalties
A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
Serving rides of equal importance for time-limited dial-a-ride
A note on the prize collecting traveling salesman problem
On the integrality gap of the prize-collecting Steiner forest LP
An improved approximation guarantee for prize-collecting TSP
An Efficient Approximation Algorithm for the Steiner Tree Problem
A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
A simple rounding scheme for multistage optimization
Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
The fractional prize-collecting Steiner tree problem on trees (extended abstract)
Variations of the prize‐collecting Steiner tree problem
scientific article; zbMATH DE number 1445375 (Why is no real title available?)
An improved algorithm for the Steiner tree problem with bounded edge-length
FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
Approximating minimum-cost connected \(T\)-joins
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
On the Exact Solution of Prize-Collecting Steiner Tree Problems
Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
Robust optimization for routing problems on trees
A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
Prize-collecting TSP with a budget constraint
A 3/2-approximation algorithm for some minimum-cost graph problems
A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
LP-based algorithms for multistage minimization problems
Approximation algorithms for group prize-collecting and location-routing problems
Solving Steiner trees: Recent advances, challenges, and perspectives
Exact approaches for solving robust prize-collecting Steiner tree problems
Approximation algorithms for prize-collecting capacitated network design problems
Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
Elementary approximation algorithms for prize collecting Steiner tree problems
Complexity and approximation for traveling salesman problems with profits
Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”
Maximizing the number of rides served for time-limited Dial-a-Ride*
An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
The prize-collecting call control problem on weighted lines and rings

This page was built for publication: Improved approximation algorithms for prize-collecting Steiner tree and TSP

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