pith. sign in

arxiv: 1907.00605 · v1 · pith:UL6XGKGEnew · submitted 2019-07-01 · 💻 cs.DS

Online Multidimensional Packing Problems in the Random-Order Model

David Naori (1) , Danny Raz (1) ((1) Computer Science Department , Technion , Israel) This is my paper

Pith reviewed 2026-05-25 11:44 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmsgeneralized assignment problemrandom-order modelmultidimensional packingcompetitive analysiscloud computingsecretary problem
0
0 comments X

The pith

A novel technique yields O(d)-competitive algorithms for the d-dimensional generalized assignment problem in the random-order model, with a matching Ω(d) lower bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that online multidimensional packing problems, specifically the d-dimensional generalized assignment problem, admit O(d)-competitive algorithms when items arrive in random order. This model is used because worst-case adversarial arrivals provide no guarantees for problems extending the secretary problem, yet it fits applications like assigning virtual machines with multiple resource requirements to physical servers. The authors introduce a technique that achieves the O(d) ratio, prove a matching Ω(d) lower bound, and show that the same approach improves the best-known ratios for the one-dimensional generalized assignment and knapsack problems.

Core claim

In the random-order model, a novel technique achieves an O(d)-competitive algorithm for the d-dimensional generalized assignment problem and the authors prove a matching lower bound of Ω(d). The technique also improves upon the best-known competitive ratios for the online one-dimensional generalized assignment problem and the online knapsack problem.

What carries the argument

A novel technique that leverages random-order arrivals to produce an O(d)-competitive algorithm for multidimensional assignment.

If this is right

  • The d-dimensional generalized assignment problem admits an O(d)-competitive algorithm under random order.
  • The competitive ratio is tight up to constants, as shown by the Ω(d) lower bound.
  • The same technique yields improved ratios for the one-dimensional generalized assignment problem and the knapsack problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear dependence on dimension may still be practical for moderate d in cloud resource allocation.
  • Similar random-order techniques could apply to other multi-resource online packing problems beyond assignment.
  • The lower bound indicates that dimension-linear loss is unavoidable in the worst case over random permutations.

Load-bearing premise

The random-order model accurately captures the arrival process for the target applications, allowing the competitive analysis to hold without adversarial ordering.

What would settle it

A concrete family of d-dimensional instances in which every online algorithm in random order has competitive ratio worse than c*d for some constant c, or in which the presented algorithm exceeds O(d).

read the original abstract

We study online multidimensional variants of the generalized assignment problem which are used to model prominent real-world applications, such as the assignment of virtual machines with multiple resource requirements to physical infrastructure in cloud computing. These problems can be seen as an extension of the well known secretary problem and thus the standard online worst-case model cannot provide any performance guarantee. The prevailing model in this case is the random-order model, which provides a useful realistic and robust alternative. Using this model, we study the $d$-dimensional generalized assignment problem, where we introduce a novel technique that achieves an $O(d)$-competitive algorithms and prove a matching lower bound of $\Omega(d)$. Furthermore, our algorithm improves upon the best-known competitive-ratio for the online (one-dimensional) generalized assignment problem and the online knapsack problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies online d-dimensional generalized assignment problems (GAP) and related packing problems in the random-order model. It introduces a novel technique yielding an O(d)-competitive algorithm for the d-dimensional case, establishes a matching Ω(d) lower bound, and improves the best-known ratios for the one-dimensional GAP and online knapsack problems.

Significance. If the claimed O(d) ratio and matching lower bound hold, the work is significant: it supplies the first tight competitive-ratio result for multidimensional online packing under random order (a model appropriate for applications such as cloud VM assignment where adversarial order yields no guarantee) and improves the 1D state of the art. The paper credits a novel algorithmic technique and supplies both upper and lower bounds.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'achieves an O(d)-competitive algorithms' contains a grammatical error and should read 'algorithm'.
  2. [Abstract / Introduction] The abstract states the existence of the O(d) algorithm and Ω(d) lower bound but supplies no proof sketch or high-level technique description; the introduction or §2 should include a concise outline of the novel technique to aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on online multidimensional GAP and related packing problems in the random-order model. We are pleased that the significance of the O(d)-competitive algorithm, the matching lower bound, and the improvements to the 1D cases are recognized. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives an O(d)-competitive algorithm for d-dimensional online GAP in the random-order model together with an explicit Ω(d) lower bound. These results rest on standard competitive analysis and random-order assumptions rather than any self-definitional reduction, fitted-input prediction, or load-bearing self-citation chain. The algorithm design, ratio proof, and lower-bound construction are presented as independent steps whose validity can be checked externally against the model definition; no equation or claim reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Limited to abstract; no explicit free parameters or invented entities visible. Relies on standard random-order model assumption and competitive analysis framework from prior secretary-problem literature.

axioms (1)
  • domain assumption Items arrive in uniformly random order.
    Central modeling choice enabling non-adversarial analysis; stated in abstract as prevailing model.

pith-pipeline@v0.9.0 · 5668 in / 1019 out tokens · 21219 ms · 2026-05-25T11:44:42.906536+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 1 internal anchor

  1. [1]

    Online vertex-weighted bipartite matching and single-bid budgeted allocations

    Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranya k Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. I n Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Alg orithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 , pages 1253–1264. SIAM, 2011

    work page 2011

  2. [2]

    A Dynamic Near-Optimal Algorithm for Online Linear Programming

    Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near -optimal algorithm for online linear programming. CoRR, abs/0911.2974, 2009

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  3. [3]

    Bruce S hepherd

    Yossi Azar, Ilan Reuven Cohen, Seny Kamara, and F. Bruce S hepherd. Tight bounds for online vector bin packing. In Dan Boneh, Tim Roughgarden, an d Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 961–970. ACM, 2013

    work page 2013

  4. [4]

    A knapsack secretary problem with applications

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Moses Charikar, Klaus Jansen , Omer Reingold, and Jos´ e D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimiza tion. Algorithms and Techniques, 10th International Workshop, APPROX 2007, a nd 11th International Wor...

    work page 2007

  5. [5]

    M atroids, secretary problems, and online mechanisms

    Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. M atroids, secretary problems, and online mechanisms. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algor ithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007 , pages 434–443. SIAM, 2007

    work page 2007

  6. [6]

    Secretary p roblems via linear programming

    Niv Buchbinder, Kamal Jain, and Mohit Singh. Secretary p roblems via linear programming. Math. Oper. Res. , 39(1):190–206, 2014

    work page 2014

  7. [7]

    On multi-dimension al packing problems

    Chandra Chekuri and Sanjeev Khanna. On multi-dimension al packing problems. In Robert En- dre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, 17-19 January 1999, Baltimore , Maryland, USA. , pages 185–194. ACM/SIAM, 1999. 15

    work page 1999

  8. [8]

    Dean, Michel X

    Brian C. Dean, Michel X. Goemans, and Jan Vondr´ ak. Adapt ivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Colum bia, Canada, January 23-25, 2005, pages 395–404. SIAM, 2005

    work page 2005

  9. [9]

    The optimum choice of the instant for sto pping a markov process

    Eugene B Dynkin. The optimum choice of the instant for sto pping a markov process. Soviet Mathematics, 4:627–629, 1963

    work page 1963

  10. [10]

    Mirrokni, and Clifford Stein

    Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online stochastic packing applied to display ad allocation. In Mar k de Berg and Ulrich Meyer, editors, Algorithms - ESA 2010, 18th Annual European Symposium, Liver pool, UK, September 6-8,

    work page 2010

  11. [11]

    Springer, 2010

    Proceedings, Part I , volume 6346 of Lecture Notes in Computer Science , pages 182–194. Springer, 2010

    work page 2010

  12. [12]

    Resource constrained scheduling as generalized bin packing

    Michael R Garey, Ronald L Graham, David S Johnson, and An drew Chi-Chih Yao. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A , 21(3):257–298, 1976

    work page 1976

  13. [13]

    An optimal online algorithm for weighted bipartite matching and extensions t o combinatorial auctions

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and B erthold V¨ ocking. An optimal online algorithm for weighted bipartite matching and extensions t o combinatorial auctions. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume...

    work page 2013

  14. [14]

    Primal beats dual on online packing lps in the random-order model

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and B erthold V¨ ocking. Primal beats dual on online packing lps in the random-order model. SIAM J. Comput. , 47(5):1939–1964, 2018

    work page 1939

  15. [15]

    Kleinberg

    Robert D. Kleinberg. A multiple-choice secretary algo rithm with applications to online auc- tions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Dis crete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-2 5, 2005 , pages 630–631. SIAM, 2005

    work page 2005

  16. [16]

    Lehmann, and Noam Nisan

    Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combi natorial auctions with decreasing marginal utilities. Games and Economic Behavior , 55(2):270–296, 2006

    work page 2006

  17. [17]

    Dynamic programming and decision theo ry

    Denis V Lindley. Dynamic programming and decision theo ry. Journal of the Royal Statistical Society: Series C (Applied Statistics) , 10(1):39–51, 1961

    work page 1961

  18. [18]

    Vazirani, and Vija y V

    Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vija y V. Vazirani. Adwords and gen- eralized online matching. J. ACM , 54(5):22, 2007

    work page 2007

  19. [19]

    Marco Molinaro and R. Ravi. Geometry of online packing l inear programs. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, edit ors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, War wick, UK, July 9-13, 2012, Proceedings, Part I , volume 7391 of Lecture Notes in Computer Science , pages 701–713. S...

    work page 2012

  20. [20]

    Linear degree extractors and the inap proximability of max clique and chromatic number

    David Zuckerman. Linear degree extractors and the inap proximability of max clique and chromatic number. Theory of Computing , 3(1):103–128, 2007. 16

    work page 2007