Using fractional primal-dual to schedule split intervals with demands

DOI10.1016/J.DISOPT.2006.05.010MaRDI QIDQ865744zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsschedulingprimal-duallocal ratio\(t\)-intervals

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Algorithms – ESA 2005
• scientific article; zbMATH DE number 2119734
• Scheduling split intervals with non-uniform demands
• Scheduling Split Intervals
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305512 (Why is no real title available?)
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A General Approximation Technique for Constrained Forest Problems
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• A unified approach to approximating resource allocation and scheduling
• Admission control in networks with advance reservations
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• Greedy approximations of independent sets in low degree graphs
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• 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
• 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
• On the complexity of approximating \(k\)-dimensional matching
• 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
• Optimization, approximation, and complexity classes
• Recognizing graphs with fixed interval number is NP-complete
• The primal-dual method for approximation algorithms

Cited in

(5)

• Online selection of intervals and t-intervals
• Scheduling split intervals with non-uniform demands
• Algorithms – ESA 2005
• Admission control with advance reservations in simple networks
• Distributed fractional local ratio and independent set approximation

This page was built for publication: Using fractional primal-dual to schedule split intervals with demands

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