Using fractional primal-dual to schedule split intervals with demands

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

zbMATH Keywords

schedulingapproximation algorithmsprimal-duallocal ratio\(t\)-intervals

Mathematics Subject Classification ID

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