Online set packing

DOI10.1137/110820774MaRDI QIDQ3143291zbMATH OpenOpenAlexFDO

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

Publication date 29 November 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110820774

zbMATH Keywords

competitive analysismultipacket framesonline set packingpacket fragmentationrandomized algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• Online set packing and competitive scheduling of multi-part tasks
• scientific article; zbMATH DE number 6696496
• Online primal-dual algorithms for covering and packing
• Online constrained optimization with recourse
• The online set cover problem

Cited in

(17)

• Scheduling multipacket frames with frame deadlines
• Distributed approximation of k-service assignment
• Competitive router scheduling with structured data
• A fast approximation algorithm for solving the complete set packing problem
• Shrinking maxima, decreasing costs: new online packing and covering problems
• scientific article; zbMATH DE number 6696496 (Why is no real title available?)
• Online packing with gradually improving capacity estimations and applications to network lifetime maximization
• Streaming algorithms for independent sets in sparse hypergraphs
• Distributed Testing of Distance-k Colorings
• Online set packing and competitive scheduling of multi-part tasks
• Online Mixed Packing and Covering
• Approximation and Online Algorithms
• Overflow management with self-eliminations
• Simple and local independent set approximation
• Overflow management with self-eliminations
• Comparing the hardness of online minimization and maximization problems with predictions
• Solving the set packing problem via a maximum weighted independent set heuristic

This page was built for publication: Online set packing

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