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
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 changed | Where | Measured | Effect |
|---|---|---|---|
| Use the one-pass Simple Online Algorithm instead of solving the LP with Gurobi | Online LP · Worst-case online LP, m=8, n=10^3 | CPU time: 0.082 -> 0.023 | Improved |
| Use the one-pass Simple Online Algorithm instead of the Dynamic Learning Algorithm | Online LP · Worst-case online LP, m=8, n=10^3 | Cmpt. Ratio: 89.8% -> 99.1% | Improved |
| Use step size 1/√t instead of 1/√n (ablation) | Simple Online Algorithm · Multi-knapsack, m=5, n=500 | Cmpt. 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 experiment | constraint violation: zero constraint violation | Improved |
| Use the feasible variant instead of the simple algorithm (ablation) | Simple Online Algorithm · Uniform i.i.d. numerical experiment | regret | Hurt |
| Use the nonstationary update based on remaining resources (ablation) | Simple Online Algorithm · Uniform i.i.d. numerical experiment | regret | Improved |
| Use a nonstationary update based on remaining resources (ablation) | Simple Online Algorithm · Numerical experiments | regret | Improved |
| Increase the truncation threshold of the Cauchy input distribution | Simple Online Algorithm and compared algorithms · Cauchy i.i.d. numerical experiment | regret | Hurt |
| Use the proposed Simple Online Algorithm instead of the slower LP-solving algorithms | Online LP · Worst-case example and Multi-knapsack benchmark | computational efficiency | Improved |
| Use the Simple Online Algorithm with γ=1/√n instead of γ=1/√t (ablation) | Simple Online Algorithm · Uniform i.i.d. numerical experiment | regret | Improved |
| Use the Simple Online Algorithm with γ=1/√n instead of γ=1/√t (ablation) | Simple Online Algorithm · Uniform i.i.d. numerical experiment | constraint violation | Hurt |
| Use the Simple Online Algorithm with γ=1/√n on random-permutation inputs (ablation) | Simple Online Algorithm · Randomly permuted input experiment | constraint violation | Hurt |
Closest papers by meaning
- Wait-Less Offline Tuning and Re-solving for Online Decision Making (ICML 2025 · similarity 0.89)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.88)
- Solving Linear Programs with Fast Online Learning Algorithms (ICML 2023 · similarity 0.88)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.86)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.85)
- Contextual Decision-Making with Knapsacks Beyond the Worst Case (NeurIPS 2024 · similarity 0.85)
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.
