Allocating Bandwidth for Bursty Connections

DOI10.1137/S0097539797329142zbMath0979.05098MaRDI QIDQ4507345

Éva Tardos, Yuval Rabani, Jon M. Kleinberg

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797329142

zbMATH Keywords

combinatorial optimization; approximation algorithms; stochastic knapsack; statistical multiplexing; effective bandwidth; stochastic load balancing; stochastic bin-packing

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes, Unnamed Item, Stochastic Load Balancing on Unrelated Machines, Worst-Case Expected Shortfall with Univariate and Bivariate Marginals, Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract), Extremal Probability Bounds in Combinatorial Optimization, Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms, Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems, An improved mechanism for selfish bin packing, Maximum box problem on stochastic points, Adaptive Bin Packing with Overflow, Configuration balancing for stochastic requests, Approximation algorithms for stochastic combinatorial optimization problems, Robust optimization approach for a chance-constrained binary knapsack problem, Stochastic models for budget optimization in search-based advertising, Approximation algorithms for multiprocessor scheduling under uncertainty, The static stochastic knapsack problem with normally distributed item sizes, The structure and complexity of Nash equilibria for a selfish routing game, Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem, Lifting of probabilistic cover inequalities, Range-max queries on uncertain data, Stochastic makespan minimization in structured set systems, An introduction to stochastic bin packing-based server consolidation with conflicts, A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes, Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity, Temporal flows in temporal networks, Hedging uncertainty: approximation algorithms for stochastic optimization problems, The multi-Handler knapsack problem under uncertainty, Mathematical models and approximate solution approaches for the stochastic bin packing problem, Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals, Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes