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
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
