Competitive router scheduling with structured data

DOI10.1016/J.TCS.2014.02.019MaRDI QIDQ2440162zbMATH OpenOpenAlexWikidataFDO

Authors Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz

Publication date 27 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.02.019

zbMATH Keywords

randomized algorithmscompetitive analysispacket fragmentation

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Competitive router scheduling with structured data
• Online set packing and competitive scheduling of multi-part tasks
• Overflow management with self-eliminations
• Overflow management with self-eliminations
• Optimal Node Routing

Cites work

• A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
• Buffer overflow management in QoS switches
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Competitive buffer management with packet dependencies
• Independent sets with domination constraints
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• On the complexity of approximating \(k\)-dimensional matching
• Online set packing
• Optimal smoothing schedules for real-time streams (extended abstract)
• Shrinking maxima, decreasing costs: new online packing and covering problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(6)

• Shrinking maxima, decreasing costs: new online packing and covering problems
• Overflow management with self-eliminations
• Overflow management with self-eliminations
• Better bounds for online \(k\)-frame throughput maximization in network switches
• Online set packing and competitive scheduling of multi-part tasks
• Competitive router scheduling with structured data

This page was built for publication: Competitive router scheduling with structured data

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