Online Set Packing

DOI10.1137/110820774zbMath1286.68488OpenAlexW2132569943MaRDI QIDQ3143291

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

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 analysisrandomized algorithmonline set packingpacket fragmentationmultipacket frames

Mathematics Subject Classification ID

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

Related Items (11)

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Distributed Testing of Distance-k Colorings ⋮ Scheduling multipacket frames with frame deadlines ⋮ Competitive router scheduling with structured data ⋮ Distributed approximation of \(k\)-service assignment ⋮ Simple and local independent set approximation ⋮ A fast approximation algorithm for solving the complete set packing problem ⋮ Overflow management with self-eliminations ⋮ Overflow management with self-eliminations

This page was built for publication: Online Set Packing