Simple and Fast Algorithm for Binary Integer and Online Linear Programming

Understand

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.