Improved algorithms for resource allocation under varying capacity

DOI10.1007/S10951-017-0515-3MaRDI QIDQ1617284zbMATH OpenOpenAlexFDO

Authors Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, Shalmoli Gupta, Sambudha Roy, Yogish Sabharwal

Publication date 7 November 2018

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-017-0515-3

zbMATH Keywords

approximation algorithmunsplittable flow problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Improved algorithms for resource allocation under varying capacity
• A unified approach to approximating resource allocation and scheduling
• A unified approach to approximating resource allocation and scheduling
• Resource allocation with time intervals
• scientific article; zbMATH DE number 2086936

Cites work

• A constant factor approximation algorithm for unsplittable flow on paths
• A logarithmic approximation for unsplittable flow on line graphs
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• A quasi-PTAS for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• Approximating the throughput of multiple machines in real-time scheduling
• Approximation algorithms for the unsplittable flow problem
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Constant integrality gap LP formulations of unsplittable flow on a path
• Distributed algorithms for scheduling on line and tree networks
• Elimination graphs
• Fast primal-dual distributed algorithms for scheduling and matching problems
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 2065154 (Why is no real title available?)
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• Improved approximation algorithms for unsplittable flow on a path with time windows
• Interval selection: Applications, algorithms, and lower bounds
• Label placement by maximum independent set in rectangles
• Maximum independent set of rectangles
• Multi-phase algorithms for throughput maximization for real-time scheduling
• Multicommodity demand flow in a tree and packing integer programs
• On the approximability of an interval scheduling problem
• Optimal packing and covering in the plane are NP-complete
• Submodular unsplittable flow on trees
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

Cited in

(6)

• A new algorithm for the available transfer capability determination
• Scheduling split intervals with non-uniform demands
• Improved algorithms for resource allocation under varying capacity
• Resource allocation for covering time varying demands
• The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users
• Scheduling resource allocation with timeslot penalty for changeover

This page was built for publication: Improved algorithms for resource allocation under varying capacity

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