The Online Set Cover Problem
From MaRDI portal
Publication:3558005
DOI10.1137/060661946zbMath1200.68271OpenAlexW2074121653MaRDI QIDQ3558005
Noga Alon, Joseph (Seffi) Naor, Baruch Awerbuch, Niv Buchbinder, Yossi Azar
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060661946
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (41)
Tight bounds for online weighted tree augmentation ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Online unit clustering and unit covering in higher dimensions ⋮ Online Allocation and Pricing with Economies of Scale ⋮ Towards the price of leasing online ⋮ Learning to compute the metric dimension of graphs ⋮ Towards Flexible Demands in Online Leasing Problems ⋮ Improved analysis of the online set cover problem with advice ⋮ Online Buy-at-Bulk Network Design ⋮ Online regenerator placement ⋮ Randomized Online Algorithms for Set Cover Leasing Problems ⋮ Online set multicover algorithms for dynamic D2D communications ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ The online broadcast range-assignment problem ⋮ The advice complexity of a class of hard online problems ⋮ Unnamed Item ⋮ Hitting geometric objects online via points in \(\mathbb{Z}^d\) ⋮ Online and Approximate Network Construction from Bounded Connectivity Constraints ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Online and approximate network construction from bounded connectivity constraints ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Online maximum \(k\)-coverage ⋮ Online sum-radii clustering ⋮ Frequency capping in online advertising ⋮ Online budgeted maximum coverage ⋮ Towards flexible demands in online leasing problems ⋮ The Online Broadcast Range-Assignment Problem ⋮ Network construction with subgraph connectivity constraints ⋮ Approximating the online set multicover problems via randomized winnowing ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Unnamed Item ⋮ Approximating Sparse Covering Integer Programs Online ⋮ Unnamed Item ⋮ Non-cooperative Cost Sharing Games Via Subsidies ⋮ Hitting sets online and unique-MAX coloring ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ Online unit covering in Euclidean space ⋮ Tight Bounds for Online Weighted Tree Augmentation ⋮ Unnamed Item ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ Online algorithms for the maximum \(k\)-interval coverage problem
This page was built for publication: The Online Set Cover Problem
