A new approximation technique for resource-allocation problems

DOI10.1002/RSA.20756MaRDI QIDQ4584915zbMATH OpenOpenAlexFDO

Authors Barna Saha, Aravind Srinivasan

Publication date 5 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20756

zbMATH Keywords

approximation algorithmsintegrality gaprandomized algorithmsroundingscheduling

Mathematics Subject Classification ID

Random walks on graphs (05C81) Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• An improved approximation algorithm for \textsc{Resource Allocation}
• Dependent rounding and its applications to approximation algorithms
• scientific article; zbMATH DE number 2086936
• A unified approach to approximating resource allocation and scheduling
• A unified approach to approximating resource allocation and scheduling

Cited in

(21)

• An efficient algorithm for the parametric resource allocation problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• A population-based fast algorithm for a billion-dimensional resource allocation problem with integer variables
• REFING: heuristic to solve bi-objective resource allocation problem with bound and varying capacity
• Multistage online maxmin allocation of indivisible entities
• General max-min fair allocation
• New Approximation Results for Resource Replication Problems
• An improved approximation algorithm for \textsc{Resource Allocation}
• Improved Approximation Algorithms for Budgeted Allocations
• Dependent rounding and its applications to approximation algorithms
• On Resource Allocation Problems with Interval-Scale Coefficients
• Solving a class of two-resource allocation problem by equivalent load method
• A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
• An approximate solution to the linear problem of minimizing resource consumption
• scientific article; zbMATH DE number 7758357 (Why is no real title available?)
• Resource time-sharing for IoT applications with deadlines
• Polynomial-time combinatorial algorithm for general max-min fair allocation
• Approximating weighted completion time via stronger negative correlation
• Time-sharing scheduling with tolerance capacities
• The budgeted maximin share allocation problem
• A new impossibility result for online bipartite matching problems

This page was built for publication: A new approximation technique for resource-allocation problems

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