An optimal local approximation algorithm for max-min linear programs

Patrik Floreen, Joel Kaasinen, Petteri Kaski, Jukka Suomela

    Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

    Sammanfattning

    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.
    Originalspråkengelska
    Titel på gästpublikationSPAA’09 : Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada
    RedaktörerFriedhelm Meyer auf der Heide, Michael A. Bender
    Antal sidor10
    FörlagACM
    Utgivningsdatum2009
    Sidor260-269
    ISBN (tryckt)978-1-60558-606-9
    DOI
    StatusPublicerad - 2009
    MoE-publikationstypA4 Artikel i en konferenspublikation
    Evenemang21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) - Calgary, Kanada
    Varaktighet: 11 aug 200913 aug 2009

    Vetenskapsgrenar

    • 113 Data- och informationsvetenskap

    Citera det här