Using fractional primal-dual to schedule split intervals with demands

DOI10.1016/J.DISOPT.2006.05.010zbMATH Open1112.90018OpenAlexW2005527711MaRDI QIDQ865744FDOQ865744

Reuven Bar-Yehuda, Dror Rawitz

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

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

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)

Cites Work

• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Title not available (Why is that?)
• A General Approximation Technique for Constrained Forest Problems
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• Greedy approximations of independent sets in low degree graphs
• Title not available (Why is that?)
• A unified approach to approximating resource allocation and scheduling
• 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
• Title not available (Why is that?)
• 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
• On approximation properties of the Independent set problem for degree 3 graphs
• Title not available (Why is that?)
• Admission control in networks with advance reservations
• Title not available (Why is that?)
• Recognizing graphs with fixed interval number is NP-complete
• The primal-dual method for approximation algorithms
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

Cited In (4)

• 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

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)