Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Online Job Assignment

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes that online job assignment has asymptotic competitive ratio $\ln(RD)$, with Forward-Looking BALANCE matching it and a lower bound showing no online algorithm can do better.

desk verdict A genuinely new online allocation algorithm with a solid integer-duration proof; the real-duration theorem needs e-companion cleanup but the stress-test's sign-error claim misreads the formula. read the letter →

arxiv 2506.06893 v1 pith:YTGBNU4N submitted 2025-06-07 cs.DS cs.GT

Farbod Ekbatani , Yiding Feng , Ian Kash , Rad Niazadeh This is my paper
classification cs.DScs.GT MSC 68W2790B3590C0590C27
keywords onlinejobassignmentreusableresourcescompetitiveanalysisprimal-dualmethodconfigurationLPforward-lookingBALANCEcloudcomputinglarge-capacityregime
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Online job assignment asks a platform to place jobs on servers as they arrive, with each job occupying a server for its duration and earning reward at completion. The paper claims that in the large-capacity regime the best possible competitive ratio against an omniscient offline benchmark has leading term $\ln(RD)$, where $R$ and $D$ are the ratios of maximum to minimum rewards and durations. It proves the upper bound by exhibiting a family of algorithms, Forward-Looking BALANCE (FLB), that assigns each job to the server maximizing an adjusted reward: the job's reward minus penalties for projected capacity use at a chosen set of current and future inspection times. It proves the lower bound by constructing single-server instances on which every online algorithm loses a $\ln(RD)+\Omega(1)$ factor. Together these give $C^*_{\mathrm{LOG\text{-}LIMIT}}=1$: no algorithm can asymptotically improve the constant in front of $\ln(RD)$.

What carries the argument

The load-bearing object is the Forward-Looking BALANCE score: for a job-server pair, $r_{ij}d_{ij} - \sum_{\tau \in \mathcal{T}_{ij}(\gamma)} \Psi(\alpha_{i,t_j\to\tau})$, where $\alpha_{i,t_j\to\tau}$ is the projected fraction of server $i$'s capacity that remains free at future time $\tau$, $\mathcal{T}_{ij}(\gamma)$ samples current and future inspection times at frequency $\gamma$, and $\Psi(x)=\eta(\beta^{1-x}-1)$ is an exponential penalty. The algorithm assigns the arriving job to the compatible server with the largest positive adjusted reward. The analysis couples this score with a configuration LP whose primal variables assign whole feasible schedules of non-overlapping jobs to units of capacity; the dual solution is built from FLB's decisions, and a charging argument verifies dual feasibility. A separate inductive invariant bounds how much the projected available capacity can drop over any duration window, which is what guarantees capacity feasibility without forcing an overly pessimistic penalty at zero capacity.

What would settle it

Take the paper's adversarial family from Section 5: a single server, jobs numbered by $j\in[M]$ arriving at $j/M$ with reward $R^{j/M}$ and duration $\lfloor D^{j/M}\rfloor$, with the adversary choosing the stopping time $k$ after seeing the online policy. Compute the worst-case ratio of FLB with the Section EC.2.3 parameters as $M$ and $c_{\min}$ grow; if it exceeds $\ln(RD)+3\ln\ln(R\vee D)+O(1)$, the upper bound is false. Similarly, if any online policy achieves a ratio below $\ln(RD)+\Omega(1)$ on this family, the lower bound is false.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the online job assignment problem has a sharp asymptotic logarithmic constant: the best competitive ratio any online algorithm can guarantee is $\ln(RD)+o(\ln(RD))$, and FLB attains $\ln(RD)+3\ln\ln(R\vee D)+O(1)$. The algorithm is a forward-looking generalization of BALANCE: instead of using only the current free capacity of each server, it subtracts from the reward the sum of an exponential penalty evaluated on the projected free capacity at inspection times inside the job's holding interval, so a server that will be busy soon looks less attractive. Feasibility is not forced by a conservative penalty at zero capacity; it follows from an invariant maintained by the algorithm. The matching lower bound holds even for fractional or randomized algorithms, via a single-server construction with exponentially increasing rewards and durations and an adversarial stopping time.

Load-bearing premise

The guarantee assumes the algorithm knows the reward range $R$ and the duration range $D$ before choosing its penalty parameters, and it is stated in the limit as server capacity grows; the paper itself shows that an algorithm without $(R,D)$ knowledge loses the logarithmic bound.

Editorial extensions

If this is right

  • For a cloud platform that knows $R$ and $D$, running FLB with the paper's parameter choices yields, for large capacity, total reward at least $(\ln(RD)+3\ln\ln(R\vee D)+O(1))^{-1}$ times the offline optimum; the leading dependence on problem heterogeneity is a single logarithm of the product $RD$.
  • No online algorithm, including randomized and fractional ones, can achieve an asymptotic logarithmic constant below 1, so the $\ln(RD)$ factor is an intrinsic price of immediacy and uncertainty, not an artifact of FLB.
  • With fixed rewards ($R=1$), the bound tightens to $\ln(D)+O(1)$, and with integer durations the second-order term improves to $\ln\ln(R\vee D)$, so the practical cost of duration heterogeneity is only logarithmic.
  • The configuration-LP dual-fitting proof and the invariant-based feasibility argument are not tied to this specific primitive family; they provide a template for other interval-occupancy allocation problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the same score were used with a soft-capacity cost rather than a hard rejection rule, the proof's invariant suggests the $\ln(RD)$ leading constant would survive as long as the penalty reflects projected occupancy; a platform that can momentarily overload a server could trade a bounded violation for higher reward.
  • The paper's $(R,D)$-agnostic lower bounds imply that even a crude estimate of reward and duration ranges, updated online, could remove the exponential gap; designing such an estimator and proving a regret-style competitive ratio is a natural next step.
  • Because the integer-duration analysis beats the real-duration bound by a $\ln\ln(R\vee D)$ factor, forcing durations onto a discrete grid may be a cheap practical lever: systems that charge in fixed time increments inherit the stronger guarantee.
  • A finite-capacity version of the parameter optimization is sketched in the paper; automating that choice per capacity level could turn FLB into a deployable policy for small clouds where $c_{\min}$ is not large.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies an adversarial online resource-allocation problem in which jobs with heterogeneous rewards and durations arrive over continuous time and must be assigned immediately and irrevocably to servers with reusable capacity. The authors propose Forward-Looking BALANCE (FLB), a parametric family of greedy algorithms that use an exponential penalty function of projected future utilizations, evaluated at a chosen set of inspection times. The main claims are an asymptotic competitive ratio of ln(RD)+3lnln(R∨D)+O(1) for general real-valued durations, a stronger ln(RD)+lnln(R∨D)+O(1) bound for integer durations, matching lower bounds up to lower-order terms, and hence C*_LOG-LIMIT = 1. The analysis is based on a configuration-LP dual fitting argument and an invariant-based capacity-feasibility proof; the paper also includes special-case results for homogeneous rewards and numerical experiments.

Significance. If correct, the paper would settle the asymptotic logarithmic constant for this heterogeneous reusable-resource model, generalize BALANCE to heterogeneous rewards and durations, and introduce a configuration-LP + invariant framework that is likely to be useful beyond this specific problem. The integer-duration analysis (Section 4) is detailed and appears internally consistent on inspection; the lower-bound construction via Yao's lemma is a clear strength, and the numerical experiments add useful evidence. However, the proof of the headline real-duration upper bound (Theorem 3.1) is not supported as written: the displayed capacity-feasibility condition in Proposition 4.10 contains an undefined logarithm for the paper's own parameter choices, and the proof of Theorem 3.1 uses a different expression. Because this issue is load-bearing for the main theorem, the general result currently lacks a valid written proof.

major comments (3)
  1. [Proposition 4.10 / EC.2.3 (proof of Theorem 3.1)] The capacity-feasibility constraint in Proposition 4.10 contains the term -ln(1 + (γ+R/η)(1 - ((ηγ+R)lnβ)/(R cmin)) - (R/η)(1+η/(R+γη))^γ). With the parameter choices made in the proof of Theorem 3.1 in EC.2.3, namely γ=⌈ln(R∨D)⌉∨2 and η=(1/ln(R∨D))^2, the quantity q=1+η/(R+γη) satisfies q^γ>1 for R∨D sufficiently large; for instance R=D=10 gives γ=3, η≈0.189 and the logarithm's argument is approximately -57.8. A logarithm of a negative number is undefined, so this constraint cannot be used to select β. Furthermore, the proof of Theorem 3.1 in EC.2.3 silently bounds the same term by -ln(1+γ+(R/η)(1-(1+η/(R+γη))^γ)), a different expression that drops the negative contributions involving q^γ. Because the claimed bound lnβ=ln(RD)+3lnln(R∨D)+O(1) is obtained by making this constraint bind, Theorem 3.1's upper bound is not derived from the stated propositions as written. The formula must be corrected and the proof re-derived before the general real-duration result can be accepted.
  2. [EC.2.2, proof of Proposition 4.11] The proof of Proposition 4.11 opens by saying it upper bounds FLB with inspection-frequency scalar γ∈(0,1], whereas the proposition statement and the program P_FLB-REAL require γ≥2. The factor γ/(γ-1) and the bound |T_ij\{τ}|≥γ-1 used in Step (ii) are false or undefined for γ∈(0,1], so this is not a cosmetic typo. In the same proof, the partition of T_iS is defined circularly: T^(a)_iS ≜ T_iS \ T^(a)_iS. These two issues make the approximate dual-feasibility argument uncheckable as written and need to be fixed.
  3. [Proposition 5.1] The lower bound is essential for the corollary C*_LOG-LIMIT=1, but as written the proof works with capacity c=1 and then asserts, without proof, that duplicating jobs extends the result to large capacities. Since Definition 2.3 defines the asymptotic competitive ratio as a limsup over cmin→∞, the c=1 construction alone does not establish the stated asymptotic lower bound. The scaling argument should be spelled out, or the statement should be restricted to the unit-capacity regime.
minor comments (5)
  1. [EC.2.2, proof of Proposition 4.11] In the explicit construction of σ, the definition σ(j,τ)≜{(jℓ,τℓ)}ℓ∈[m] should range over ℓ∈[s], where s=c_i-c_iα_i,t_j→τ; as printed the image set has cardinality m rather than s.
  2. [EC.2.1, proof of Lemma EC.2.1] In Case (ii), the notation switches between t, τ, and t_j, and the derivation of the displayed lower bound is very hard to follow. The proof should be rewritten with consistent time variables, especially since it is a load-bearing part of the real-duration argument.
  3. [Proposition 4.10 / P_FLB-REAL] The program P_FLB-REAL states η>0, but Proposition 4.10 says (η,β)∈R_+^2 even though the expression R/η appears. The case η=0 should be excluded explicitly.
  4. [Section 6.2] The description of the truncated normal distribution says rewards and durations are 'bounded within [0,10]', but the model normalizes rewards and durations to be at least 1. It should be clarified whether normalization is applied after truncation and how the reported R=D=10 is enforced.
  5. [Section 4.1, Lemma 4.4] The footnote after the lemma statement imposes a condition on β, η, cmin that is later used in the proof; placing this condition before the lemma statement and integrating it into the lemma's hypotheses would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the competitive-ratio upper bounds are derived by dual fitting against an independent configuration LP, the lower bound uses a concrete Yao-style instance family, and the algorithm parameters are selected by solving the resulting constraint programs rather than fitted to the claimed result.

full rationale

The paper's derivation chain is self-contained and non-circular. The upper bound (Theorem 3.1) is obtained from two independently stated ingredients: a capacity-feasibility condition (Proposition 4.10, based on the inductive invariant in Lemma EC.2.1) and a primal-dual competitive-ratio bound against the configuration LP relaxation P_OPT (Proposition 4.11). The configuration LP is shown in Lemma 4.7 to upper bound the optimal offline benchmark, and the dual solution is constructed explicitly from FLB's assignments, with feasibility proved by a charging argument. The lower bound (Proposition 5.1) is an independent Yao-lemma construction on a single-server instance family; it does not invoke FLB or any parameter values. Parameter choices in the proof of Theorem 3.1 (gamma = ceil(ln(R∨D))∨2, eta = (1/ln(R∨D))^2, and beta set so that the P_FLB-REAL constraint binds) are solutions of a displayed optimization program, not quantities fitted to the target ln(RD)+3lnln(R∨D)+O(1) bound. The e/(e-1) R=D=1 case is attributed to prior work including Karp et al. and Goyal et al., and is also independently recovered by the same optimization program, so the self-citations to Feng et al. are not load-bearing. No step reduces the claimed theorem to an assumption of the theorem. A possible algebraic/sign issue in the displayed real-duration feasibility expression in Proposition 4.10 would be a proof-correctness concern, not a circularity concern, because it concerns whether the written derivation is valid rather than whether a 'prediction' is equivalent to its input by construction.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The central claim rests on bounded heterogeneity (Assumption 2.1), prior knowledge of R,D, the large-capacity asymptotic definition, and standard tools (Yao's lemma, LP duality). The algorithm's parameters (γ,η,β) are chosen by hand to satisfy feasibility and optimize the bound; they are not fitted to empirical data.

free parameters (3)
  • β (penalty base) = Set so the capacity-feasibility constraint binds; β=e in bounded regimes
    Chosen by hand in Theorem 4.1 and EC.2.3 to satisfy Proposition 4.2 or 4.10 conditions while minimizing the competitive-ratio expression.
  • η (penalty scale) = 1/ln(R∨D) for ln(R∨D)≥e−1; R/(e−1) otherwise
    Chosen by hand in the proofs of Theorems 4.1 and 3.1 to balance the feasibility constraint and the objective.
  • γ (inspection frequency) = 1 for integer durations; ⌈ln(R∨D)⌉∨2 for real durations; ∞ for fixed-reward case
    Chosen per regime to ensure capacity feasibility and approximate dual feasibility with factor γ/(γ−1).
assumptions (5)
  • domain assumption Bounded heterogeneity: r_ij ∈ [1,R] and d_ij ∈ [1,D] for every compatible pair (i,j).
    Assumption 2.1, needed for finite competitive ratios; minima are normalized to 1.
  • domain assumption The online algorithm knows R and D in advance.
    Remark 2.2; EC.5 shows agnostic algorithms cannot achieve logarithmic bounds.
  • domain assumption Large-capacity asymptotic regime: competitive ratio is defined as limsup over instances as cmin→∞.
    Definition 2.3; all headline bounds are asymptotic in cmin.
  • standard math Yao's lemma is valid for randomized lower bounds.
    Used in Proposition 5.1 to derive a distribution-based lower bound.
  • standard math Weak duality for the configuration LP holds.
    Lemma 4.7 establishes P_OPT as a relaxation, and weak duality certifies the primal-dual ratio.
invented entities (2)
  • Inspection-time subset T_ij(γ)
    purpose: Selects future times during a job's duration at which projected capacity is penalized; implements the forward-looking feature.
    An algorithmic primitive introduced by the paper; its justification is internal to the competitive-ratio analysis, and no external evidence is claimed.
  • Configuration LP P_OPT
    purpose: Relaxation of the offline optimum in which each capacity unit is assigned a set of non-overlapping jobs; used for dual fitting.
    A mathematical construct used to prove tight competitive ratios; it has no falsifiable handle outside the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Job Assignment." pith.science (2026). https://pith.science/paper/YTGBNU4N

@misc{pith2026250606893,
  author       = {Pith},
  title        = {Pith review of: Online Job Assignment},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YTGBNU4N}},
  note         = {Machine review of arXiv:2506.06893}
}
read the original abstract

Motivated primarily by applications in cloud computing, we study a simple, yet powerful, online allocation problem in which jobs of varying durations arrive over continuous time and must be assigned immediately and irrevocably to one of the available offline servers. Each server has a fixed initial capacity, with assigned jobs occupying one unit for their duration and releasing it upon completion. The algorithm earns a reward for each assignment upon completion. We consider a general heterogeneous setting where both the reward and duration of a job depend on the job-server pair. The objective of the online algorithm is to maximize the total collected reward, and remain competitive against an omniscient benchmark that knows all job arrivals in advance. Our main contribution is the design of a new online algorithm, termed Forward-Looking BALANCE (FLB), and using primal-dual framework to establish that it is (asymptotically) optimal-competitive. This meta-algorithm has two main primitives: (i) keeping track of the capacity used for each server at each time and applying a penalty function to this quantity, and (ii) adjusting the reward of assigning a job to a server by subtracting the total penalty of a particularly chosen subset of future times, in contrast to just looking at the current time. The FLB algorithm then assigns the arriving job to the server with the maximum adjusted reward. If R and D are the ratios of maximum over minimum rewards and durations, we show that the FLB algorithm obtains an asymptotic competitive ratio of ln(RD)+3lnln(max(R,D))+O(1). We further show this bound has optimal dependencies on all the parameters. Our main analysis combines a novel dual-fitting technique, which leverages the configuration LP benchmark for this problem, and a novel inductive argument to establish the capacity feasibility of the algorithm, which might be of independent interest.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Stationary Online Contention Resolution Schemes

    cs.GT 2026-03 conditional novelty 7.0 of 10

    Stationary OCRSs—order-independent online rounding—achieve optimal 0.382 selectability for bipartite matchings, Poisson-optimal guarantees for k-uniform matroids, and explicit 1/2 selectability for weakly Rayleigh matroids.

Reference graph

Works this paper leans on

61 extracted references · 59 canonical work pages · cited by 1 Pith paper

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.se...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

    work page

  3. [3]

    Combinatorial auctions with restricted complements

    Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, and Tim Roughgarden. Combinatorial auctions with restricted complements. In Boi Faltings, Kevin Leyton - Brown, and Panos Ipeirotis, editors, Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012 , pages 3--16. ACM , 2012

    work page 2012

  4. [4]

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

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

    work page 2011

  5. [5]

    Real-time personalized order holding

    Mohammad Reza Aminian, Will Ma, and Linwei Xin. Real-time personalized order holding. Available at SSRN 4644495, 2023

    work page 2023

  6. [6]

    A nonparametric framework for online stochastic matching with correlated arrivals

    Ali Aouad and Will Ma. A nonparametric framework for online stochastic matching with correlated arrivals. In Kevin Leyton - Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023 , page 114. ACM , 2023

    work page 2023

  7. [7]

    Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin. Throughput-competitive on-line routing. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 32--40. IEEE Computer Society, 1993

    work page 1993

  8. [8]

    Plotkin, Kirk Pruhs, and Orli Waarts

    Yossi Azar, Bala Kalyanasundaram, Serge A. Plotkin, Kirk Pruhs, and Orli Waarts. On-line load balancing of temporary tasks. Journal of Algorithms, 22 0 (1): 0 93--110, 1997

    work page 1997

Show all 61 references
  1. [9]

    Truthful online scheduling with commitments

    Yossi Azar, Inna Kalp - Shaltiel, Brendan Lucier, Ishai Menache, Joseph Naor, and Jonathan Yaniv. Truthful online scheduling with commitments. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computa...

    2015

  2. [10]

    Yossi Azar, Niv Buchbinder, T. - H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, and Debmalya Panigrahi. Online algorithms for covering and packing problems with convex objectives. In Irit Dinur, editor, I...

    2016

  3. [11]

    Ball and Maurice Queyranne

    Michael O. Ball and Maurice Queyranne. Toward robust revenue management: Competitive analysis of online booking. Operations Research, 57 0 (4): 0 950--963, 2009

    2009

  4. [12]

    Improved approximation algorithms for multidimensional bin packing problems

    Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. Improved approximation algorithms for multidimensional bin packing problems. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings , pages 6...

    2006

  5. [13]

    Incentive compatible mulit-unit combinatorial auctions: A primal dual approach

    Niv Buchbinder and Rica Gonen. Incentive compatible mulit-unit combinatorial auctions: A primal dual approach. Algorithmica, 72 0 (1): 0 167--190, 2015

    2015

  6. [14]

    Online primal-dual algorithms for covering and packing

    Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34 0 (2): 0 270--286, 2009

    2009

  7. [15]

    Online primal-dual algorithms for maximizing ad-auctions revenue

    Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings , volume...

    2007

  8. [16]

    Bounding the power of preemption in randomized scheduling

    Ran Canetti and Sandy Irani. Bounding the power of preemption in randomized scheduling. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC '95, page 606–615, New York, NY, USA, 1995. Association for Computing Machinery. ISBN 0897917189

    1995

  9. [17]

    Devanur, Alexander E

    Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan. Stability of service under time-of-use pricing. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium ...

    2017

  10. [18]

    Benjamin Miller, and Yifeng Teng

    Shuchi Chawla, J. Benjamin Miller, and Yifeng Teng. Pricing for online resource allocation: Intervals and paths. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 ...

    2019

  11. [19]

    Learning-augmented online bipartite fractional matching

    Davin Choo, Billy Jin, and Yongho Shin. Learning-augmented online bipartite fractional matching. arXiv preprint arXiv:2505.19252, 2025

    2025

  12. [20]

    Online bipartite matching with reusable resources

    Steven Delong, Alireza Farhadi, Rad Niazadeh, Balasubramanian Sivan, and Rajan Udwani. Online bipartite matching with reusable resources. Mathematics of Operations Research, 49 0 (3): 0 1825--1854, 2024

    2024

  13. [21]

    Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A

    Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66 0 (1): 0 7:1--7:41, 2019

    2019

  14. [22]

    The trim problem

    Kurt Eisemann. The trim problem. Management Science, 3 0 (3): 0 279--284, 1957. ISSN 00251909, 15265501

    1957

  15. [23]

    Online resource allocation with buyback: Optimal algorithms via primal-dual

    Farbod Ekbatani, Yiding Feng, and Rad Niazadeh. Online resource allocation with buyback: Optimal algorithms via primal-dual. In Kevin Leyton - Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, ...

    2023

  16. [24]

    Mirrokni, S

    Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin P \' a l. Online ad assignment with free disposal. In Stefano Leonardi, editor, Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings , v...

    2009

  17. [25]

    Batching and optimal multistage bipartite allocations

    Yiding Feng and Rad Niazadeh. Batching and optimal multistage bipartite allocations. Management Science, 71 0 (5): 0 4108--4130, 2025

    2025

  18. [26]

    Linear programming based online policies for real-time assortment of reusable resources

    Yiding Feng, Rad Niazadeh, and Amin Saberi. Linear programming based online policies for real-time assortment of reusable resources. Chicago Booth Research Paper, 2019

    2019

  19. [27]

    Robustness of online inventory balancing algorithm to inventory shocks

    Yiding Feng, Rad Niazadeh, and Amin Saberi. Robustness of online inventory balancing algorithm to inventory shocks. Available at SSRN 3795056, 2021

    2021

  20. [28]

    Online learning and capacity management in cloud-cost optimization

    Zhichao Feng, Milind Dawande, Ganesh Janakiraman, and Anyan Qi. Online learning and capacity management in cloud-cost optimization. Available at SSRN 4812792, 2024

    2024

  21. [29]

    Real-time optimization of personalized assortments

    Negin Golrezaei, Hamid Nazerzadeh, and Paat Rusmevichientong. Real-time optimization of personalized assortments. Management Science, 60 0 (6): 0 1532--1551, 2014

    2014

  22. [30]

    Iyengar, David Simchi - Levi, Rajan Udwani, and Shuangyu Wang

    Xiao - Yue Gong, Vineet Goyal, Garud N. Iyengar, David Simchi - Levi, Rajan Udwani, and Shuangyu Wang. Online assortment optimization with reusable resources. Management Science, 68 0 (7): 0 4772--4785, 2022

    2022

  23. [31]

    Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation

    Vineet Goyal and Rajan Udwani. Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Operations Research, 71 0 (2): 0 563--580, 2023

    2023

  24. [32]

    Asymptotically optimal competitive ratio for online allocation of reusable resources

    Vineet Goyal, Garud Iyengar, and Rajan Udwani. Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research, 0 0 (0): 0 0, 2025

    2025

  25. [33]

    Dynamic server provisioning to minimize cost in an iaas cloud

    Yu - Ju Hong, Jiachen Xue, and Mithuna Thottethodi. Dynamic server provisioning to minimize cost in an iaas cloud. In Arif Merchant, Kimberly Keeton, and Dan Rubenstein, editors, SIGMETRICS 2011, Proceedings of the 2011 ACM SIGMETRICS International Conference on Measurement an...

    2011

  26. [34]

    Online stochastic matching, poisson arrivals, and the natural linear program

    Zhiyi Huang and Xinkai Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pa...

    2021

  27. [35]

    Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue

    Zhiyi Huang and Qiankun Zhang. Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue. SIAM Journal on Computing, 53 0 (5): 0 1217--1256, 2024

    2024

  28. [36]

    Online matching with stochastic rewards: Advanced analyses using configuration linear programs

    Zhiyi Huang, Hanrui Jiang, Aocheng Shen, Junkai Song, Zhiang Wu, and Qiankun Zhang. Online matching with stochastic rewards: Advanced analyses using configuration linear programs. In Jugal Garg, Max Klimm, and Yuqing Kong, editors, Web and Internet Economics - 19th Internation...

    2023

  29. [37]

    Adwords in a panorama

    Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. SIAM Journal on Computing, 53 0 (3): 0 701--763, 2024

    2024

  30. [38]

    Online reusable resource allocations with multi-class arrivals

    Tianming Huo and Wang Chi Cheung. Online reusable resource allocations with multi-class arrivals. Available at SSRN 4320423, 2022

    2022

  31. [39]

    Vazirani

    Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP . Journal of the ACM (JACM), 50 0 (6): 0 795--824, 2003

    2003

  32. [40]

    Online learning and pricing for service systems with reusable resources

    Huiwen Jia, Cong Shi, and Siqian Shen. Online learning and pricing for service systems with reusable resources. Operations Research, 72 0 (3): 0 1203--1241, 2024

    2024

  33. [41]

    An optimal deterministic algorithm for online b-matching

    Bala Kalyanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233 0 (1-2): 0 319--325, 2000

    2000

  34. [42]

    Karp, Umesh V

    Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA , pages 352--358. ACM , 1990

    1990

  35. [43]

    Kash, Peter B

    Ian A. Kash, Peter B. Key, and Warut Suksompong. Simple pricing schemes for the cloud. ACM Transactions on Economics and Computation (TEAC), 7 0 (2): 0 7:1--7:27, 2019

    2019

  36. [44]

    Lipton and Andrew Tomkins

    Richard J. Lipton and Andrew Tomkins. Online interval scheduling. In Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA , pages 302--311. ACM/SIAM , 1994

    1994

  37. [45]

    Efficient online scheduling for deadline-sensitive jobs: Extended abstract

    Brendan Lucier, Ishai Menache, Joseph (Seffi) Naor, and Jonathan Yaniv. Efficient online scheduling for deadline-sensitive jobs: Extended abstract. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, page 305–314, N...

    2013

  38. [46]

    Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios

    Will Ma and David Simchi - Levi. Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Operations Research, 68 0 (6): 0 1787--1803, 2020

    2020

  39. [47]

    Allocating online advertisement space with unreliable estimates

    Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Proceedings of the 8th ACM conference on Electronic commerce, pages 288--294, 2007

    2007

  40. [48]

    Online algorithms for matching platforms with multichannel traffic

    Vahideh Manshadi, Scott Rodilitz, Daniela Saban, and Akshaya Suresh. Online algorithms for matching platforms with multichannel traffic. Management Science, 0 0 (0): 0 0, 2025

    2025

  41. [49]

    Vazirani, and Vijay V

    Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54 0 (5): 0 22, 2007

    2007

  42. [50]

    Online primal-dual algorithms with configuration linear programs

    Kim Thang Nguyen. Online primal-dual algorithms with configuration linear programs. In Yixin Cao, Siu - Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference) , vo...

    2020

  43. [51]

    Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals

    Paat Rusmevichientong, Mika Sumida, Huseyin Topaloglu, and Yicheng Bai. Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals. Operations Research, 71 0 (6): 0 2196--2216, 2023

    2023

  44. [52]

    On greedy-like policies in online matching with reusable network resources and decaying rewards

    David Simchi-Levi, Zeyu Zheng, and Feng Zhu. On greedy-like policies in online matching with reusable network resources and decaying rewards. Management Science, 0 0 (0): 0 0, 2025

    2025

  45. [53]

    Adwords with unknown budgets and beyond

    Rajan Udwani. Adwords with unknown budgets and beyond. Management Science, 71 0 (2): 0 1009--1026, 2025

    2025

  46. [54]

    On the configuration-lp for scheduling on unrelated machines

    Jos \' e Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. Journal of Scheduling, 17 0 (4): 0 371--383, 2014

    2014

  47. [55]

    Selling reserved instances in cloud computing

    Changjun Wang, Weidong Ma, Tao Qin, Xujin Chen, Xiaodong Hu, and Tie - Yan Liu. Selling reserved instances in cloud computing. In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 20...

    2015

  48. [56]

    Dynamic cloud resource reservation via cloud brokerage

    Wei Wang, Di Niu, Baochun Li, and Ben Liang. Dynamic cloud resource reservation via cloud brokerage. In IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013, 8-11 July, 2013, Philadelphia, Pennsylvania, USA , pages 400--409. IEEE Computer Society, 2013

    2013

  49. [57]

    Probabilistic computations: Toward a unified measure of complexity (extended abstract)

    Andrew Chi - Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 222--227. IEEE Computer Society, 1977

    1977

  50. [58]

    An online mechanism for dynamic VM provisioning and allocation in clouds

    Sharrukh Zaman and Daniel Grosu. An online mechanism for dynamic VM provisioning and allocation in clouds. In Rong Chang, editor, 2012 IEEE Fifth International Conference on Cloud Computing, Honolulu, HI, USA, June 24-29, 2012 , pages 253--260. IEEE Computer Society, 2012

    2012

  51. [59]

    Vasilakos, and Jiangchuan Liu

    Hong Zhang, Hongbo Jiang, Bo Li, Fangming Liu, Athanasios V. Vasilakos, and Jiangchuan Liu. A framework for truthful online auctions in cloud computing with heterogeneous user demands. IEEE Transactions on Computers, 65 0 (3): 0 805--818, 2016 a

    2016

  52. [60]

    Randomized mechanisms for selling reserved instances in cloud computing

    Jia Zhang, Weidong Ma, Tao Qin, Xiaoming Sun, and Tie - Yan Liu. Randomized mechanisms for selling reserved instances in cloud computing. In Satinder Singh and Shaul Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, ...

    2017

  53. [61]

    Online resource scheduling under concave pricing for cloud computing

    Rui Zhang, Kui Wu, Minming Li, and Jianping Wang. Online resource scheduling under concave pricing for cloud computing. IEEE Transactions on Parallel and Distributed Systems, 27 0 (4): 0 1131--1145, 2016 b

    2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.