Approximation algorithms for prize-collecting capacitated network design problems

DOI10.1007/978-3-031-20796-9_16zbMath1524.90328OpenAlexW4313349037MaRDI QIDQ6111480

Chi Kit Ken Fong, Vincent Chau, Lu Han

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 designSteiner treeprize-collecting

Mathematics Subject Classification ID

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

Cites Work

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

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