Improved approximation algorithms for constrained fault-tolerant resource allocation

DOI10.1016/j.tcs.2015.02.029zbMath1327.68335OpenAlexW4229891353MaRDI QIDQ2348043

Hong Shen, Kewen Liao, Longkun Guo

Publication date: 10 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.029

zbMATH Keywords

reductionresource allocationtime complexityapproximation algorithmsprimal-dualLP-rounding

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• LP-rounding algorithms for the fault-tolerant facility placement problem
• Approximation algorithms for the fault-tolerant facility placement problem
• Combinatorial optimization. Theory and applications.
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Unconstrained and Constrained Fault-Tolerant Resource Allocation
• Approximation Algorithms for Metric Facility Location Problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm
• A new greedy approach for facility location problems
• The Fault-Tolerant Facility Allocation Problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• A constant factor approximation algorithm for the fault-tolerant facility location problem
• Fault-tolerant facility location
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem