Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties

DOI10.1142/S0129054117500320zbMath1387.68300OpenAlexW2788168460MaRDI QIDQ4639927

Vaishali M. Wadhwa, Deepak Garg

Publication date: 14 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054117500320

zbMATH Keywords

resource allocationprimal-dual approximationtime dependent penalty

Mathematics Subject Classification ID

Mixed integer programming (90C11) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• Approximation algorithm for facility location with service installation costs
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• The \(k\)-level facility location game
• 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
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Analysis of a Local Search Heuristic for Facility Location Problems