Scheduling split intervals with non-uniform demands

DOI10.1016/j.disopt.2020.100611zbMath1506.90094OpenAlexW3082946749MaRDI QIDQ2218651

Yogish Sabharwal, Sambuddha Roy, Venkatesan T. Chakaravarthy, Anamitra R. Choudhury

Publication date: 15 January 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2020.100611

zbMATH Keywords

approximation algorithmsrandomized roundingunsplittable flow problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cites Work

• Approximability of sparse integer programs
• The interval number of a planar graph: Three intervals suffice
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation algorithms for the unsplittable flow problem
• Scheduling jobs with fixed start and end times
• Geometric algorithms and combinatorial optimization.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Improved algorithms for resource allocation under varying capacity
• On the complexity of approximating \(k\)-set packing
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• A quasi-PTAS for unsplittable flow on line graphs
• Algorithmic aspects of bandwidth trading
• Kernelization Algorithms for Packing Problems Allowing Overlaps
• Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
• On double and multiple interval graphs
• Extremal Values of the Interval Number of a Graph
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On Multidimensional Packing Problems
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• Scheduling Split Intervals
• Algorithms – ESA 2005
• A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
• A unified approach to approximating resource allocation and scheduling
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Scheduling split intervals with non-uniform demands