Online Lower Bounds via Duality
From MaRDI portal
Publication:4575806
DOI10.1137/1.9781611974782.66zbMath1410.68138arXiv1604.01697OpenAlexW2339454087MaRDI QIDQ4575806
Alan Roytman, Ilan Reuven Cohen, Yossi Azar
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.01697
Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items
Online unit clustering and unit covering in higher dimensions, Approximation and online algorithms for multidimensional bin packing: a survey, Online bin packing with cardinality constraints resolved, Online ad allocation in bounded-degree graphs, Approximation algorithms for the partial assignment problem, Online algorithms for maximum cardinality matching with edge arrivals, Unnamed Item, Lower bounds for online bin covering-type problems, Online Algorithms for Maximum Cardinality Matching with Edge Arrivals, Randomized strategies for non-additive 3-slope ski rental
