Approximation algorithm for resource allocation problems with time dependent penalties

DOI10.1142/S0129054117500320MaRDI QIDQ4639927zbMATH OpenOpenAlexFDO

Authors 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

primal-dual approximationresource allocationtime dependent penalty

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5811147
• Approximation algorithms for the priority facility location problem with penalties
• An improved approximation algorithm for \textsc{Resource Allocation}
• Improved approximation algorithms for constrained fault-tolerant resource allocation (extended abstract)
• scientific article; zbMATH DE number 2086936

Cites work

• 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
• Algorithms for facility location problems with outliers. (Extended abstract)
• An approximation algorithm for the k-level capacitated facility location problem
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation algorithm for facility location with service installation costs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation Algorithms for Metric Facility Location Problems
• Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 2086926 (Why is no real title available?)
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Network design for information networks
• The \(k\)-level facility location game

Cited in

(3)

• Material allocation in MRP with tardiness penalties
• scientific article; zbMATH DE number 5035881 (Why is no real title available?)
• Resource holding times: Computation and optimization

This page was built for publication: Approximation algorithm for resource allocation problems with time dependent penalties

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