Approximation algorithms for group prize-collecting and location-routing problems

DOI10.1016/J.DAM.2008.05.013MaRDI QIDQ1003471zbMATH OpenOpenAlexFDO

Authors Hagai Glicksman, Michal Penn

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.05.013

zbMATH Keywords

algorithmlocationapproximationgrouptravelling salesmanprize-collecting

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Recommendations

• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Elementary approximation algorithms for prize collecting Steiner tree problems
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• scientific article; zbMATH DE number 1303564
• scientific article; zbMATH DE number 1445375

Cites work

• scientific article; zbMATH DE number 3470175 (Why is no real title available?)
• scientific article; zbMATH DE number 2064416 (Why is no real title available?)
• scientific article; zbMATH DE number 219265 (Why is no real title available?)
• scientific article; zbMATH DE number 2119643 (Why is no real title available?)
• scientific article; zbMATH DE number 3298367 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• A note on the prize collecting traveling salesman problem
• An application of simultaneous diophantine approximation in combinatorial optimization
• An efficient transformation of the generalized vehicle routing problem
• Approximation algorithm for the group Steiner network problem
• Generalized Steiner problems and other variants
• Generalized network design problems.
• Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
• Geometric algorithms and combinatorial optimization
• Hamiltonian location problems
• On the generalized minimum spanning tree problem
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• The prize collecting traveling salesman problem
• Transformations of generalized ATSP into ATSP.

Cited in

(6)

• A survey of recent research on location-routing problems
• A branch-and-cut algorithm for the windy profitable location rural postman problem
• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• scientific article; zbMATH DE number 6297719 (Why is no real title available?)
• A survey of variants and extensions of the location-routing problem
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties

This page was built for publication: Approximation algorithms for group prize-collecting and location-routing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003471)