# Simple and Fast Algorithm for Binary Integer and Online Linear Programming

arXiv: https://arxiv.org/abs/2003.02513 · HTML: https://mlsanity.com/paper/2003.02513/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2020.

## Built on by (most cited first, 27 of 27)

- [Towards Better Statistical Understanding of Watermarking LLMs](https://mlsanity.com/paper/2403.13027/) (2024)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [MoE-SpAc: Efficient MoE Inference Based on Speculative Activation Utility in Heterogeneous Edge Scenarios](https://mlsanity.com/paper/2603.09983/) (2026)
- [Online Learning for Traffic Routing under Unknown Preferences](https://mlsanity.com/paper/2203.17150/) (2022)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent](https://mlsanity.com/paper/2202.06152/) (2022)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Trading-off price for data quality to achieve fair online allocation](https://mlsanity.com/paper/2306.13440/) (2023)
- [Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networks](https://mlsanity.com/paper/2212.03659/) (2022)
- [An Online Algorithm for Chance Constrained Resource Allocation](https://mlsanity.com/paper/2303.03254/) (2023)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)
- [Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics](https://mlsanity.com/paper/2605.01280/) (2026)
- [Online Allocation Problem with Two-sided Resource Constraints](https://mlsanity.com/paper/2112.13964/) (2021)
- [A General Traffic Shaping Protocol in E-Commerce](https://mlsanity.com/paper/2112.14941/) (2021)
- [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023)
- [GreenFlow: A Computation Allocation Framework for Building Environmentally Sound Recommendation System](https://mlsanity.com/paper/2312.16176/) (2023)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)
- [Online Linear Programming for Multi-Objective Routing in LLM Serving](https://mlsanity.com/paper/2607.03948/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm in two different models, stochastic input and random permutation, with minimal technical assumptions on the input data. The algorithm achieves Oleft(m √nright) expected regret under the stochastic input model and Oleft((m+log n)√nright) expected regret under the random permutation model, and it achieves O(m √n) expected constraint violation under both models, where n is the number of decision variables and m is the number of constraints. The algorithm enjoys the same performance guarantee when generalized to a multi-dimensional LP setting which covers a wider range of applications. In addition, we employ the notion of permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound with a factor of √m by paying more computational cost. Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms.