A guessing game and randomized online algorithms

DOI10.1145/335305.335385MaRDI QIDQ3192029zbMATH OpenOpenAlexFDO

Authors Steven S. Seiden

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• Randomized algorithms for on-line scheduling problems: How low can't you go?
• A lower bound for randomized list update algorithms
• On randomization in on-line computation.
• scientific article; zbMATH DE number 1003270
• A lower bound for randomized on-line scheduling algorithms

Cited in

(21)

• LP-based online scheduling: From single to parallel machines
• Online scheduling with general machine cost functions
• Dynamic TCP acknowledgment and other stories about e/(e-1)
• News from the online traveling repairman.
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Preemptively guessing the center
• Preemptive online algorithms for scheduling with machine cost
• Two short notes on the on-line travelling salesman: handling times and lookahead.
• New results on multi-level aggregation
• Guessing fractions of online sequences
• An optimal online algorithm for scheduling with general machine cost functions
• Online scheduling with machine cost and rejection
• Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost
• Parameter learning algorithm for the online data acknowledgment problem
• Online Algorithms for Multilevel Aggregation
• Uniform parallel machine scheduling problems with fixed machine cost
• Traveling repairperson, unrelated machines, and other stories about average completion times
• Online multi-level aggregation with delays and stochastic arrivals
• Competitive analysis of the online leasing problem with a piecewise price function
• On the remote server problem or more about TCP acknowledgments
• New lower bounds for online k-server routing problems

This page was built for publication: A guessing game and randomized online algorithms

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