检索结果-内蒙古大学图书馆

28th Annual ACM Symposium on Principles of distributed Computing

作者： Awerbuch, Baruch Fu, Zhenghua Khandekar, Rohit Johns Hopkins Univ Baltimore MD 21218 USA

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.

关键词： distributed and stateless algorithms gradient descent fast convergence linear programming

来源：评论

学校读者我要写书评

暂无评论

stateless distributed GRADIENT DESCENT FOR POSITIVE LINEAR PROGRAMS

引用

SIAM JOURNAL ON COMPUTING 2009年第6期38卷 2468-2486页

作者： Awerbuch, Baruch Khandekar, Rohit Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA IBM TJ Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA

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

关键词： distributed and stateless algorithms gradient descent fast convergence linear programming

来源：评论

学校读者我要写书评

暂无评论

stateless distributed Gradient Descent for Positive Linear Programs 08

Stateless Distributed Gradient Descent for Positive Linear P...

引用

14th Annual ACM International Symposium on Theory of Computing

作者： Awerbuch, Baruch Khandekar, Rohit Johns Hopkins Univ Baltimore MD 21218 USA IBM Corp TJ Watson Res Ctr Armonk NY 10504 USA

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.

关键词： distributed and stateless algorithms gradient descent fast convergence linear programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：