Approximation algorithms for prize-collecting capacitated network design problems

DOI10.1007/978-3-031-20796-9_16MaRDI QIDQ6111480zbMATH OpenOpenAlexFDO

Authors Lu Han, Vincent Chau, Chi Kit Ken Fong

Publication date 3 August 2023

Published in Frontiers of Algorithmic Wisdom (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-20796-9_16

zbMATH Keywords

approximation algorithmfacility locationnetwork designprize-collectingSteiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for a capacitated network design problem
• Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
• scientific article; zbMATH DE number 1670539
• Approximability of capacitated network design
• scientific article; zbMATH DE number 1003253

Cites work

• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• A General Approximation Technique for Constrained Forest Problems
• A local search approximation algorithm for the uniform capacitated k-facility location problem
• A note on the prize collecting traveling salesman problem
• Algorithms - ESA 2003
• Algorithms for facility location problems with outliers. (Extended abstract)
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• Approximation algorithms for supply chain planning and logistics problems with market choice
• Approximation algorithms for the robust facility leasing problem
• Improved approximation algorithm for universal facility location problem with linear penalties
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Primal-dual algorithms for connected facility location problems
• Prize-collecting Steiner networks via iterative rounding
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

Cited in

(2)

• Approximation algorithms for a capacitated network design problem
• A MIP-based approach to solve the prize-collecting local access network design problem

This page was built for publication: Approximation algorithms for prize-collecting capacitated network design problems

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