AI Paper Atlas

Research map / Bandits and online learning / Online convex optimization and games

Simple and Fast Algorithm for Binary Integer and Online Linear Programming

Xiaocheng Li, Chunlin Sun, Yinyu Ye

NeurIPS 2020 · Bandits and online learning › Online convex optimization and games · approach: Online allocation with constraints · 12 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use the one-pass Simple Online Algorithm instead of solving the LP with GurobiOnline LP · Worst-case online LP, m=8, n=10^3CPU time: 0.082 -> 0.023Improved
Use the one-pass Simple Online Algorithm instead of the Dynamic Learning AlgorithmOnline LP · Worst-case online LP, m=8, n=10^3Cmpt. Ratio: 89.8% -> 99.1%Improved
Use step size 1/√t instead of 1/√n (ablation)Simple Online Algorithm · Multi-knapsack, m=5, n=500Cmpt. Ratio: 75.05% -> 92.3%Improved
Use the feasible variant that rejects requests when constraints do not permit acceptance (ablation)Simple Online Algorithm · Uniform i.i.d. numerical experimentconstraint violation: zero constraint violationImproved
Use the feasible variant instead of the simple algorithm (ablation)Simple Online Algorithm · Uniform i.i.d. numerical experimentregretHurt
Use the nonstationary update based on remaining resources (ablation)Simple Online Algorithm · Uniform i.i.d. numerical experimentregretImproved
Use a nonstationary update based on remaining resources (ablation)Simple Online Algorithm · Numerical experimentsregretImproved
Increase the truncation threshold of the Cauchy input distributionSimple Online Algorithm and compared algorithms · Cauchy i.i.d. numerical experimentregretHurt
Use the proposed Simple Online Algorithm instead of the slower LP-solving algorithmsOnline LP · Worst-case example and Multi-knapsack benchmarkcomputational efficiencyImproved
Use the Simple Online Algorithm with γ=1/√n instead of γ=1/√t (ablation)Simple Online Algorithm · Uniform i.i.d. numerical experimentregretImproved
Use the Simple Online Algorithm with γ=1/√n instead of γ=1/√t (ablation)Simple Online Algorithm · Uniform i.i.d. numerical experimentconstraint violationHurt
Use the Simple Online Algorithm with γ=1/√n on random-permutation inputs (ablation)Simple Online Algorithm · Randomly permuted input experimentconstraint violationHurt

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy