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

DOI10.1137/S009753979528826XzbMath0916.90256OpenAlexW1998678640MaRDI QIDQ4210146

Baruch Awerbuch, Santosh Vempala, Yossi Azar, Avrim L. Blum

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 algorithm prize-collecting traveling salesman problem k-MST

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Algorithms for the on-line quota traveling salesman problem ⋮ Optimal deterministic algorithms for some variants of online quota traveling salesman problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ 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 ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ 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 ⋮ Dynamic Traveling Repair Problem with an Arbitrary Time Window ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ Multi-objective meta-heuristics for the traveling salesman problem with profits ⋮ An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits ⋮ Application of fuzzy optimization to the orienteering problem ⋮ The online prize-collecting traveling salesman problem ⋮ 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 ⋮ Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Exploring and Triangulating a Region by a Swarm of Robots ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ 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