A guessing game and randomized online algorithms

DOI10.1145/335305.335385zbMath1296.68071MaRDI QIDQ3192029

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms

Related Items

Online Algorithms for Multilevel Aggregation, Uniform parallel machine scheduling problems with fixed machine cost, On the remote server problem or more about TCP acknowledgments, New lower bounds for online \(k\)-server routing problems, LP-based online scheduling: From single to parallel machines, Online scheduling with general machine cost functions, News from the online traveling repairman., Randomized algorithms for on-line scheduling problems: How low can't you go?, 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, 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