New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
- scientific article; zbMATH DE number 1263203
- Exact and approximation algorithms for the min-max \(k\)-traveling salesmen problem on a tree
- An approximation algorithm for the k-prize-collecting multicut on a tree problem
- A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
- An approximation algorithm for the B-prize-collecting multicut problem in trees
- On the prize-collecting generalized minimum spanning tree problem
- A better approximation algorithm for the budget prize collecting tree problem.
- \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
- scientific article; zbMATH DE number 1756011
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
Cited in
(38)- Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
- Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems
- Application of fuzzy optimization to the orienteering problem
- Local search algorithms for the \(k\)-cardinality tree problem.
- Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics
- A 4-approximation algorithm for k-prize collecting Steiner tree problems
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- Pruning 2-connected graphs
- Approximation algorithms for the traveling repairman and speeding deliveryman problems
- A stabilized column generation scheme for the traveling salesman subtour problem
- Complexity and approximation for traveling salesman problems with profits
- Multi-objective vehicle routing problems
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
- Networks of polynomial pieces with application to the analysis of point clouds and images
- Orienteering problem with time-windows and updating delay
- Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms
- Optimal deterministic algorithms for some variants of online quota traveling salesman problem
- Dynamic traveling repair problem with an arbitrary time window
- A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
- Exploring and triangulating a region by a swarm of robots
- scientific article; zbMATH DE number 1263203 (Why is no real title available?)
- A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
- Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
- A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
- A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
- Simple heuristics for the rooted max tree coverage problem
- A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
- A unifying framework for selective routing problems
- Additive sparsification of CSPs
- Optimal and approximated path planning for a robot moving on aisle-graphs
- Algorithms for the on-line quota traveling salesman problem
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- Multi-objective meta-heuristics for the traveling salesman problem with profits
- An exact -constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
- The online prize-collecting traveling salesman problem
- The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
This page was built for publication: New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210146)
