New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen

DOI10.1137/S009753979528826XMaRDI QIDQ4210146zbMATHOpenAlexFDO

Authors Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala

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

zbMATH Keywords

approximation algorithmprize-collecting traveling salesman problemk-MST

Mathematics Subject Classification ID

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)

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

(33)

• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
• Orienteering problem with time-windows and updating delay
• Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• Application of fuzzy optimization to the orienteering problem
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
• Simple heuristics for the rooted max tree coverage problem
• Networks of polynomial pieces with application to the analysis of point clouds and images
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics
• Dynamic traveling repair problem with an arbitrary time window
• Multi-objective vehicle routing problems
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Approximation algorithms for the traveling repairman and speeding deliveryman problems
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• The online prize-collecting traveling salesman problem
• A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
• Algorithms for the on-line quota traveling salesman problem
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• A stabilized column generation scheme for the traveling salesman subtour problem
• Exploring and triangulating a region by a swarm of robots
• 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
• An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
• Complexity and approximation for traveling salesman problems with profits
• Pruning 2-connected graphs
• Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

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)