Improved algorithms for resource allocation under varying capacity
DOI10.1007/s10951-017-0515-3zbMath1406.90036OpenAlexW2588949834MaRDI QIDQ1617284
Venkatesan T. Chakaravarthy, Sambudha Roy, Anamitra R. Choudhury, Yogish Sabharwal, Shalmoli Gupta
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
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for the unsplittable flow problem
- Optimal packing and covering in the plane are NP-complete
- Label placement by maximum independent set in rectangles
- Multi-phase algorithms for throughput maximization for real-time scheduling
- On the approximability of an interval scheduling problem
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Approximating the Throughput of Multiple Machines in Real-Time Scheduling
- Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
- 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
- Distributed algorithms for scheduling on line and tree networks
- Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
- Submodular Unsplittable Flow on Trees
- Elimination graphs
- Multicommodity demand flow in a tree and packing integer programs
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Interval selection: Applications, algorithms, and lower bounds
- Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path
- A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
- A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
- A logarithmic approximation for unsplittable flow on line graphs
- A unified approach to approximating resource allocation and scheduling
This page was built for publication: Improved algorithms for resource allocation under varying capacity
