Simple and Fast Algorithm for Binary Integer and Online Linear Programming

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 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 Omnminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O\left( m \sqrt{n}\right)$document expected regret under the stochastic input model and O(m+logn)nminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O\left( (m+\log n)\sqrt{n}\right)$document expected regret under the random permutation model, and it achieves O(mn)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O(m \sqrt{n})$document 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 the permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound by a factor of mminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\sqrt{m}$document 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.