Bayesian generalized network design

DOI10.1016/J.TCS.2020.07.010MaRDI QIDQ2202025zbMATH OpenOpenAlexFDO

Authors Yuval Emek, Shay Kutten, Ron Lavi, Yangguang Shi

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.00484, https://drops.dagstuhl.de/opus/volltexte/2019/11166/

zbMATH Keywords

Bayesian competitive ratioBayesian ignorancebest response dynamicsdiseconomies of scaleenergy consumptiongeneralized network designsmoothness

Mathematics Subject Classification ID

Bayesian problems; characterization of Bayes procedures (62C10) Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10)

Abstract: We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.'s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.

Recommendations

• Bayesian ignorance
• Bayesian ignorance
• A network design model under uncertainty
• Designing networks with good equilibria under uncertainty
• Designing networks with good equilibria under uncertainty

Cites work

• A note on two problems in connexion with graphs
• Accelerating the Benders decomposition method: application to stochastic network design problems
• Bayesian ignorance
• Energy efficient scheduling and routing via randomized rounding
• Exact Price of Anarchy for Polynomial Congestion Games
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 5764797 (Why is no real title available?)
• scientific article; zbMATH DE number 5764851 (Why is no real title available?)
• scientific article; zbMATH DE number 1303557 (Why is no real title available?)
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• Improved bounds on Bell numbers and on moments of sums of random variables
• Intrinsic robustness of the price of anarchy
• Mixing times and \(\ell_p\) bounds for oblivious routing
• Oblivious network design
• Oblivious Routing for the Lp-norm
• Potential games
• Probability inequalities of the Tchebycheff type
• Progressive hedging-based metaheuristics for stochastic network design
• Randomized oblivious integral routing for minimizing power cost
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Solving Optimization Problems with Diseconomies of Scale via Decoupling
• Speed scaling to manage energy and temperature
• Steiner tree approximation via iterative randomized rounding
• Survey on oblivious routing strategies
• The Price of Stability for Network Design with Fair Cost Allocation
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(1)

• Bayesian generalized network design

This page was built for publication: Bayesian generalized network design

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