Online scheduling with interval conflicts

DOI10.1007/S00224-012-9408-1MaRDI QIDQ372978zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz

Publication date 21 October 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2011/3036/

zbMATH Keywords

competitive analysiscompound tasksdistributed algorithmsinterval conflictsonline schedulingonline set packing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Online scheduling with interval conflicts
• scientific article; zbMATH DE number 1003261
• Scheduling with conflicts: Online and offline algorithms
• A randomized algorithm for online scheduling with interval conflicts
• Online interval scheduling to maximize total satisfaction
• Online Interval Scheduling to Maximize Total Satisfaction
• scientific article; zbMATH DE number 1834669
• Randomized online interval scheduling
• scientific article; zbMATH DE number 1670659
• On-line scheduling revisited

Cites work

• A unified approach to approximating resource allocation and scheduling
• Competitive buffer management with packet dependencies
• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 1003262 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1167865 (Why is no real title available?)
• Online primal-dual algorithms for covering and packing
• Online selection of intervals and \(t\)-intervals
• Online set packing and competitive scheduling of multi-part tasks

Cited in

(11)

• Non-clairvoyant scheduling with conflicts for unit-size jobs
• Scheduling with conflicts on bipartite and interval graphs
• Shrinking maxima, decreasing costs: new online packing and covering problems
• Online scheduling with interval conflicts
• A randomized algorithm for online scheduling with interval conflicts
• Better bounds for online \(k\)-frame throughput maximization in network switches
• Overflow management with self-eliminations
• Overflow management with self-eliminations
• Any-order online interval selection
• Scheduling with conflicts: Online and offline algorithms
• Online scheduling with reassignment

This page was built for publication: Online scheduling with interval conflicts

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