Online set packing and competitive scheduling of multi-part tasks

DOI10.1145/1835698.1835800zbMath1315.68035OpenAlexW2129881384MaRDI QIDQ5176219

Jaikumar Radhakrishnan, Yishay Mansour, Boaz Patt-Shamir, Yuval Emek, Magnús M. Halldórsson, Dror Rawitz

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1835698.1835800

zbMATH Keywords

competitive analysisonline set packingpacket fragmentationmulti-packet frames

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)

Related Items (6)

A Randomized Algorithm for Online Scheduling with Interval Conflicts ⋮ Better bounds for online \(k\)-frame throughput maximization in network switches ⋮ Online scheduling with interval conflicts ⋮ Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts ⋮ Optimal Buffer Management for 2-Frame Throughput Maximization ⋮ Online parallel scheduling of non-uniform tasks: trading failures for energy

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

This page was built for publication: Online set packing and competitive scheduling of multi-part tasks