Help
Cart
Skip main navigation

Available Issues

April 16, 2013 - May 25, 2026

Available Issues

April 16, 2013 - May 25, 2026

Interior-Point-Based Online Stochastic Bin Packing

Published Online:1 Jul 2020https://doi.org/10.1287/opre.2019.1914

References

  • Adelman D, Nemhauser GL (1999) Price-directed control of remnant inventory systems. Oper. Res. 47(6):889–898.Link, Google Scholar
  • Agrawal S, Devanur NR (2015) Fast algorithms for online stochastic convex programming. Chekuri C, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
  • Albers S, Mitzenmacher M (1998) Average-case analyses of first fit and random fit bin packing. Karloff H, ed. Proc. 9th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 290–299.Google Scholar
  • Asgeirsson EI, Stein C (2009) Bounded-space online bin cover. J. Scheduling 12(5):461–474.Crossref, Google Scholar
  • Awerbuch B, Khandekar R (2008) Stateless distributed gradient descent for positive linear programs. Proc. 40th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 691–700.Google Scholar
  • Balogh J, Békési J, Dósa G, Epstein L, Levin A (2017) A new and improved algorithm for online bin packing. Azar Y, Bast H, Herman G, eds. 26th Annual Eur. Sympos. Algorithms 112:5:1–5:14.Google Scholar
  • Balogh J, Békési J, Dósa G, Sgall J, Van Stee R (2015) The optimal absolute ratio for online bin packing. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1425–1438.Google Scholar
  • Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
  • Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, New York).Crossref, Google Scholar
  • Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. 15th Annual Eur. Conf. Algorithms (ESA) (Springer-Verlag, Berlin, Heidelberg), 253–264.Google Scholar
  • Coffman EG, Stolyar AG (2001) Bandwidth packing. Algorithmica 29(1–2):70–88.Crossref, Google Scholar
  • Coffman EG Jr, Courcoubetis C, Garey MR, Johnson DS, McGeoch LA, Shor PW, Weber RR, Yannakakis M (1991) Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin packing case study. Proc. 23rd Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 230–240.Google Scholar
  • Courcoubetis C, Weber RR (1986) Necessary and sufficient conditions for stability of a bin-packing system. J. Appl. Probab. 23(4):989–999.Crossref, Google Scholar
  • Csirik J, Woeginger GJ (2002) Resource augmentation for online bounded space bin packing. J. Algorithms 44(2):308–320.Crossref, Google Scholar
  • Csirik J, Johnson DS, Kenyon C, Shor PW, Weber RR (1999) A self organizing bin packing heuristic. Selected Papers from the International Workshop on Algorithm Engineering and Experimentation (ALENEX) (Springer-Verlag, London), 246–265.Google Scholar
  • Csirik J, Johnson DS, Kenyon C, Orlin JB, Shor PW, Weber RR (2006) On the sum-of-squares algorithm for bin packing. J. ACM 53(1):1–65.Crossref, Google Scholar
  • Esfandiari H, Korula N, Mirrokni V (2015) Online allocation with traffic spikes: Mixing adversarial and stochastic models. Proc. 16th ACM Conf. Econom. Comput. (ACM, New York), 169–186.Google Scholar
  • Gamarnik D (2004) Stochastic bandwidth packing process: Stability conditions via Lyapunov function technique. Queueing Systems 48(3–4):339–363.Crossref, Google Scholar
  • Gamarnik D, Squillante MS (2005) Analysis of stochastic online bin packing processes. Stochastic Models 21:401–425.Crossref, Google Scholar
  • Guha S, McGregor A (2006) Approximate quantiles and the order of the stream. Proc. 25th ACM SIGMOD-SIGACT-SIGART Sympos. Principles Database Systems (ACM, New York), 273–279.Google Scholar
  • Guha S, McGregor A (2007) Lower bounds for quantile estimation in random-order and multi-pass streaming. Arge L, Cachin C, Jurdzinski T, Tarlecki A, eds. Proc. Internat. Colloquium Automata Languages Programming (Springer, Berlin, Heidelberg), 704–715.Google Scholar
  • Gupta A, Molinaro M (2014). How experts can solve LPs online. Schulz AS, Wagner D, eds. Proc. 2014 Eur. Sympos. Algorithms (Springer, Berlin, Heidelberg), 517–529.Google Scholar
  • Iyengar G, Sigman K (2004) Exponential penalty function control of loss networks. Ann. Appl. Probab. 14(4):1698–1740.Crossref, Google Scholar
  • Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4):299–325.Crossref, Google Scholar
  • Karmarkar N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. Proc. 23rd Annual Sympos. Foundations Comput. Sci. (SFCS) (IEEE Computer Society, Washington, DC), 312–320.Google Scholar
  • Kenyon C, Mitzenmacher M (2002) Linear waste of best fit bin packing on skewed distributions. Random Structures Algorithms 20(3):441–464.Crossref, Google Scholar
  • Kenyon C, Rabani Y, Sinclair A (1996) Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing. Tardos E, ed. Proc. 7th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 351–358.Google Scholar
  • Lee CC, Lee D-T (1985) A simple on-line bin-packing algorithm. J. ACM 32(3):562–572.Crossref, Google Scholar
  • Leighton FT, Shor P (1986) Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms. Proc. 18th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 91–103.Google Scholar
  • Lelarge M (2007) Online bandwidth packing with symmetric distributions. DMTCS Proc. 2007 Conf. Anal. Algorithms 7:471–482.Google Scholar
  • Naaman N, Rom R (2008) Average case analysis of bounded space bin packing algorithms. Algorithmica 50(1):72–97.Crossref, Google Scholar
  • Neely MJ (2009) Delay analysis for maximal scheduling with flow control in wireless networks with bursty traffic. IEEE/ACM Trans. Networking 17(4):1146–1159.Crossref, Google Scholar
  • Neely MJ (2010) Stochastic Network Optimization with Application to Communication and Queueing Systems (Morgan & Claypool, Williston, VT).Google Scholar
  • Nemirovski A, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (John Wiley & Sons, Chichester, UK).Google Scholar
  • Plotkin SA, Shmoys DB, Tardos É (1995) Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2):257–301.Link, Google Scholar
  • Rhee WT, Talagrand M (1993) On-line bin packing of items of random sizes, II. SIAM J. Comput. 22(6):1251–1256.Google Scholar
  • Rothvoß T (2013) Approximating bin packing within o (log opt* log log opt) bins. Proc. IEEE 54th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 20–29.Google Scholar
  • Shah D, Tsitsiklis JN (2008) Bin packing with queues. J. Appl. Probab. 45(4):922–939.Crossref, Google Scholar
  • Shor PW (1986) The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6(2):179–200.Crossref, Google Scholar
  • Shor PW (1991). How to pack better than best fit: tight bounds for average-case online bin packing. Proc. 32nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 752–759.Google Scholar
  • Stolyar AL (2005) Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems Theory Appl. 50(4):401–457.Google Scholar
  • Tassiulas L, Ephremides A (1992) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control 37(12):1936–1948.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree