Non-clairvoyant scheduling with conflicts for unit-size jobs

DOI10.1016/j.ipl.2018.12.008zbMath1478.68028OpenAlexW2906349901WikidataQ128696268 ScholiaQ128696268MaRDI QIDQ1721929

Hongyang Sun

Publication date: 13 February 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.12.008

zbMATH Keywords

competitive analysisonline algorithmsmakespan minimizationconflict graphsnon-clairvoyant scheduling

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Bounds on contention management algorithms
• Scheduling with conflicts: Online and offline algorithms
• Transactional contention management as a Non-clairvoyant scheduling problem
• An on-line graph coloring algorithm with sublinear performance ratio
• A still better performance guarantee for approximate graph coloring
• Zero knowledge and the chromatic number
• Coloring inductive graphs on-line
• Lower bounds for on-line graph coloring
• Nonclairvoyant scheduling
• On chromatic sums and distributed resource allocation
• Window-based greedy contention management for transactional memory: theory and practice
• A competitive analysis for balanced transactional memory workloads
• Scheduling with conflicts on bipartite and interval graphs
• Sum Multicoloring of Graphs
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Toward a theory of transactional contention managers