A general approach to online network optimization problems

DOI10.1145/1198513.1198522zbMath1321.68509OpenAlexW1973444128MaRDI QIDQ2944534

Joseph (Seffi) Naor, Noga Alon, Niv Buchbinder, Baruch Awerbuch, Yossi Azar

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

competitive analysisfacility locationrandomized roundinggroup Steineronline network optimizationmulti-cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (23)

Online algorithms for the maximum \(k\)-colorable subgraph problem ⋮ Towards the price of leasing online ⋮ Online Buy-at-Bulk Network Design ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Timing matters: online dynamics in broadcast games ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Online sum-radii clustering ⋮ Frequency capping in online advertising ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Towards flexible demands in online leasing problems ⋮ Path-disruption games: bribery and a probabilistic model ⋮ 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 ⋮ Non-cooperative Cost Sharing Games Via Subsidies ⋮ Combinatorial optimization in system configuration design ⋮ Unnamed Item ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ Parametric Shortest-Path Algorithms via Tropical Geometry

This page was built for publication: A general approach to online network optimization problems