We develop a framework of distributed and stateless solutions for implicitly given packing linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. This is motivated by...
详细信息
ISBN:
(纸本)9781605583969
We develop a framework of distributed and stateless solutions for implicitly given packing linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. This is motivated by multi-commodity flow problems where flows can be split along possibly exponentially many paths. Compared to explicitly given packing LPs, the main challenge here lies in the exponentially (or even infinitely) many variables handled by a single agent. An efficient algorithm thus must identify a few "good" variables to update. Using a notion similar to the shortest-path-first-flow-decomposition, our algorithm discovers polynomially many variables to update in each iteration. We prove that after polynomially many rounds, the discovered variables support a near-optimal solution to the given packing LP.
We develop a framework of distributed and stateless solutions for packing and covering linear programs (LPs), which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a se...
详细信息
We develop a framework of distributed and stateless solutions for packing and covering linear programs (LPs), which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate "agent" controlling each variable, and an agent is allowed to read off the current values only of those constraints in which it has nonzero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets. The most appealing features of our algorithms are their simplicity and polylogarithmic convergence. For the packing LP max{c . x | Ax <= b, x >= 0}, the algorithm associates a dual variable y(i) = exp[1/epsilon (A(i)x/b(i)-1)] for each constraint i, and each agent j iteratively increases (resp., decreases) x(j) multiplicatively if A(j)(inverted perpendicular)y is too small (resp., large) as compared to c(j). Our algorithm, starting from a feasible solution, always maintains feasibility and computes a (1+epsilon) approximation in poly(ln(mn.A(max))/epsilon) rounds. Here m and n are number of rows and columns of A, and A(max), also known as the "width" of the LP, is the ratio of the maximum and the minimum nonzero values taken by the expression A(ij)/(b(i)c(j)) as the pair i, j varies over the matrix. A similar algorithm works for the covering LP min{b.y | A(inverted perpendicular) y >= c, y >= 0} as well. While exponential dual variables have been used in several packing/covering linear programming (LP) algorithms before [S. Plotkin, D. Shmoys, and E. Tardos, Math. Oper. Res., 20 (1995), pp. 257-301;Y. Bartal, J. W. Byers, and D. Raz, Proceedings of the IEEE Symposium on Foundations of Computer Science, 1997;N. Garg and J. Konemann, SIAM J. Comput., 37 (2007), pp. 630-652;L. K. Fleischer, SIAM J. Discrete Math., 13 (2000), pp. 505-520;N. E. Young, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2001;C. Koufogiannakis and N. E. Young, Proceedings of th
We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate...
详细信息
ISBN:
(纸本)9781605580470
We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate "agent" controlling each variable and all agent is allowed to read-off the current values only of those constraints in which it;has non-zero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets. The most appealing feature of our algorithms is their simplicity and polylogarithmic convergence. For the packing LP max{c (.) x vertical bar Ax <= b, x >= 0}, the algorithm associates a dual variable y(i) = exp[1/epsilon(A(i)x/b(i) - 1)] for each constraint i and each agent j iteratively increases (resp. decreases) x(j) multiplicatively if A(j)(T)y is too small (resp. large) as compared to c(j). Our algorithm starting from a feasible solution, always maintains feasibility, and computes a (1 + epsilon) approximation in poly(In(mn.A(max)/epsilon) rounds. Here m and n are number of rows and columns of A and A(max);also known as the "width" of the LP, is the ratio of maximum and minimum non-zero entries A(ij)/(b(i)c(j)). Similar algorithm works for the covering LP min{b (.) y vertical bar A(T)y >= c, y >= 0} as well. While exponential dual variables are used in several packing/covering LP algorithms before [25, 9, 13, 12, 26, 16], this is the first algorithm which is both stateless and has polylogarithmic convergence. Our algorithms can be thought of as applying distributed gradient descent/ascent on a, carefully chosen potential. Our analysis differs from those of previous multiplicative update based algorithms and argues that while the current solution is far away from optimality, the potential function decreases/increases by a significant factor.
暂无评论