A Solution for Minimum Link Flow Problem with Sparse Modeling

摘要

In recent years, a statistical approach called sparse modeling has been studied extensively for estimating unobserved model parameters from a small number of observations by using the sparsity of model parameters. Although sparse modeling has been applied to many practical problems in the fields of signal processing and image processing, to the best of our knowledge, few studies have applied it to the field of information networking. In this paper, we investigate how sparse modeling can be applied to a network flow problem. Specifically, we focus on the minimum link flow problem that is similar to the classical minimum cost flow problem except that its objective is to minimize the number of links consisting a flow rather than the total link cost. We present a sparsemodeling- based formulation of the minimum link flow problem and investigate how effectively our formulation of the minimum link flow problem can be solved using a conventional greedy algorithm called Orthogonal Matching Pursuit (OMP). We also extend our sparse-modeling-based approach to a constrained minimum link flow problem with finite link capacities. For solving the constrained minimum link flow problem, we propose a greedy algorithm called Constrained Orthogonal Matching Pursuit (COMP).