Patrik Floréen · Joel Kaasinen · Petteri Kaski · Jukka Suomela

An optimal local approximation algorithm for max-min linear programs

SPAA 2009 · 21st ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Canada, August 2009 · doi:10.1145/1583991.1584058

authors’ version publisher’s version arXiv.org

Abstract

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Publication

Friedhelm Meyer auf der Heide and Michael A. Bender (Eds.): SPAA’09, Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures, August 11–13, 2009, Calgary, Alberta, Canada, pages 260–269, ACM Press, New York, 2009

ISBN 978-1-60558-606-9

Links

Journal Version

© ACM 2009 — This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 21st ACM Symposium on Parallelism in Algorithms and Architectures. http://doi.acm.org/10.1145/1583991.1584058

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.