Using fractional primal-dual to schedule split intervals with demands
From MaRDI portal
Publication:865744
DOI10.1016/j.disopt.2006.05.010zbMath1112.90018OpenAlexW2005527711MaRDI QIDQ865744
Dror Rawitz, Reuven Bar Yehuda
Publication date: 20 February 2007
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2006.05.010
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (2)
Online selection of intervals and \(t\)-intervals ⋮ Admission control with advance reservations in simple networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recognizing graphs with fixed interval number is NP-complete
- Optimization, approximation, and complexity classes
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- The primal-dual method for approximation algorithms
- Admission control in networks with advance reservations
- One for the price of two: a unified approach for approximating covering problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A General Approximation Technique for Constrained Forest Problems
- On approximation properties of the Independent set problem for degree 3 graphs
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- 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)
This page was built for publication: Using fractional primal-dual to schedule split intervals with demands
