A note on the prize collecting traveling salesman problem
From MaRDI portal
Publication:687042
DOI10.1007/BF01581256zbMath0793.90089MaRDI QIDQ687042
Michel X. Goemans, David Simchi-Levi, Bienstock, Daniel, David P. Williamson
Publication date: 16 August 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
traveling salesmanapproximation algorithmundirected graphellipsoid methodguaranteed approximation ratioLP-relaxationssubtourvertex specific penalties
Related Items (80)
Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint ⋮ Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Robust optimization for routing problems on trees ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem ⋮ Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ Combinatorial Heuristics for Inventory Routing Problems ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ The rainbow Steiner tree problem ⋮ The restricted Chinese postman problems with penalties ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ Approximation algorithms for prize-collecting capacitated network design problems ⋮ Hybrid genetic algorithm for undirected traveling salesman problems with profits ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ Improved approximation algorithm for the asymmetric prize-collecting TSP ⋮ Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio ⋮ Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ A primal-dual approximation algorithm for the asymmetric prize-collecting TSP ⋮ Euclidean prize-collecting Steiner forest ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ Unnamed Item ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Algorithmic expedients for the prize collecting Steiner tree problem ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ Approximation algorithms for supply chain planning and logistics problems with market choice ⋮ On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem ⋮ Interdiction Games and Monotonicity, with Application to Knapsack Problems ⋮ A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks ⋮ Online covering salesman problem ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Weighted matching with pair restrictions ⋮ Approximating the tree and tour covers of a graph ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Online constrained forest and prize-collecting network design ⋮ Local search algorithms for the red-blue median problem ⋮ Elementary approximation algorithms for prize collecting Steiner tree problems ⋮ Supply Chain Management with Online Customer Selection ⋮ A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks ⋮ Unnamed Item ⋮ A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem ⋮ Approximation algorithms for general cluster routing problem ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements ⋮ An exact solution method for the TSP with drone based on decomposition ⋮ The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Approximation algorithms for group prize-collecting and location-routing problems ⋮ The vehicle routing-allocation problem: A unifying framework ⋮ A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs ⋮ A tabu search heuristic for the vehicle routing problem with private fleet and common carrier ⋮ Strong lower bounds for the prize collecting Steiner problem in graphs ⋮ A simple rounding scheme for multistage optimization ⋮ An improved approximation ratio for the minimum latency problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Unnamed Item ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties ⋮ Exact approaches for solving robust prize-collecting Steiner tree problems ⋮ Serving rides of equal importance for time-limited dial-a-ride ⋮ LP-based algorithms for multistage minimization problems
Cites Work
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- The prize collecting traveling salesman problem
- Heuristic analysis, linear programming and branch and bound
- On some connectivity properties of Eulerian graphs
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: A note on the prize collecting traveling salesman problem
