New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
DOI10.1137/S009753979528826XzbMATH Open0916.90256OpenAlexW1998678640MaRDI QIDQ4210146FDOQ4210146
Santosh S. Vempala, Yossi Azar, Avrim Blum, Baruch Awerbuch
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753979528826x
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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Parallel algorithms in computer science (68W10) Transportation, logistics and supply chain management (90B06)
Cited In (33)
- Orienteering problem with time-windows and updating delay
- The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
- Networks of polynomial pieces with application to the analysis of point clouds and images
- A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
- Approximation algorithms for the traveling repairman and speeding deliveryman problems
- A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- Complexity and approximation for traveling salesman problems with profits
- An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
- Pruning 2-connected graphs
- Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics
- Multi-objective meta-heuristics for the traveling salesman problem with profits
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- Optimal deterministic algorithms for some variants of online quota traveling salesman problem
- A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
- Simple heuristics for the rooted max tree coverage problem
- Dynamic Traveling Repair Problem with an Arbitrary Time Window
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- Algorithms for the on-line quota traveling salesman problem
- Local search algorithms for the \(k\)-cardinality tree problem.
- The online prize-collecting traveling salesman problem
- Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
- Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms
- A stabilized column generation scheme for the traveling salesman subtour problem
- Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems
- Application of fuzzy optimization to the orienteering problem
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Exploring and Triangulating a Region by a Swarm of Robots
- Multi-objective vehicle routing problems
- Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
- A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
- A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
- A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
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)
