An optimal local approximation algorithm for max-min linear programs
| Contribuinte(s) |
University of Helsinki, Department of Computer Science University of Helsinki, Helsinki Institute for Information Technology HIIT (-2009) University of Helsinki, Helsinki Institute for Information Technology HIIT |
|---|---|
| Data(s) |
2009
|
| Resumo |
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. |
| Formato |
10 |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
SPAA’09 Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada |
| Direitos |
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 |
| Fonte |
Floreen , P , Kaasinen , J , Kaski , P & Suomela , J 2009 , ' An optimal local approximation algorithm for max-min linear programs ' in SPAA’09 : Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada , pp. 260-269 . , 10.1145/1583991.1584058 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
