A general approach to online network optimization problems

DOI10.1145/1198513.1198522MaRDI QIDQ2944534zbMATH OpenOpenAlexFDO

Authors Noga Alon, Baruch Awerbuch, Niv Buchbinder, Joseph (Seffi) Naor, 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 locationgroup Steinermulti-cutsonline network optimizationrandomized rounding

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6469194
• Online network design algorithms via hierarchical decompositions
• The online multicommodity connected facility location problem
• Online node-weighted Steiner tree and related problems
• Online and stochastic survivable network design

Cited in

(41)

• Combinatorial optimization in system configuration design
• Online algorithms for the maximum \(k\)-colorable subgraph problem
• Towards flexible demands in online leasing problems
• Timing matters: online dynamics in broadcast games
• Online covering with \(\ell_q\)-norm objectives and applications to network design
• Network construction with subgraph connectivity constraints
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• Online sum-radii clustering
• Approximating the online set multicover problems via randomized winnowing
• Online and approximate network construction from bounded connectivity constraints
• Online network design with outliers
• Towards the price of leasing online
• Online network design with outliers
• Thresholded covering algorithms for robust and max-min optimization
• Online degree-bounded Steiner network design
• Online Buy-at-Bulk Network Design
• Frequency capping in online advertising
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Greedy algorithms for online survivable network design
• Online facility location with deletions
• Compact oblivious routing
• Network construction with ordered constraints
• Online and stochastic survivable network design
• Path-disruption games: bribery and a probabilistic model
• Approximating sparse covering integer programs online
• Online network design algorithms via hierarchical decompositions
• Non-cooperative Cost Sharing Games Via Subsidies
• scientific article; zbMATH DE number 6469194 (Why is no real title available?)
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• On-line network synthesis
• Parametric shortest-path algorithms via tropical geometry
• Online Spanners in Metric Spaces
• Online Nash welfare maximization without predictions
• Adaptive-adversary-robust algorithms via small copy tree embeddings
• Online spanners in metric spaces
• Online Euclidean spanners
• A nearly optimal deterministic online algorithm for non-metric facility location
• Approximation algorithms for directed weighted spanners
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• An approximation algorithm for generalized connectivity problem on planar graphs
• The long arm of Nashian allocation in online p-mean welfare maximization

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

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