Auction algorithms for generalized nonlinear network flow problems

TL;DRAbstract

Network flow is an area of optimization theory concerned with optimization over networks with a range of applicability in fields such as computer networks, manufacturing, finance, scheduling and routing, telecommunications, and transportation. In both linear and nonlinear networks, a family of primal-dual algorithms based on approximate Complementary Slackness (e-CS) is among the fastest in centralized and distributed environments. These include the auction algorithm for the linear assignment/transportation problems, & relaxation and Auction/Sequential Shortest Path (ASSP) for the min-cost flow and max-flow problems. Within this family, the auction algorithm is particularly fast, as it uses information, as compared to using the more generic e-relaxation for linear assignment/transportation. Inspired by the success of auction algorithms, we extend them to two important classes of nonlinear network flow problems. We start with the nonlinear Resource Allocation Problem (RAP). This probl

Chat with Paper

AI Agents for this Paper