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

DOI10.1016/J.DAM.2008.05.013zbMATH Open1155.90416OpenAlexW2011973760MaRDI QIDQ1003471FDOQ1003471

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

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

zbMATH Keywords

algorithmlocationapproximationgrouptravelling salesmanprize-collecting

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• A survey of recent research on location-routing problems
• Title not available (Why is that?)
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• A branch-and-cut algorithm for the windy profitable location rural postman problem
• A survey of variants and extensions of the location-routing problem

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)