An optimal local approximation algorithm for max-min linear programs

Patrik Floreen; Joel Kaasinen; Petteri Kaski; Jukka Suomela

doi:10.1145/1583991.1584058

An optimal local approximation algorithm for max-min linear programs

Patrik Floreen, Joel Kaasinen, Petteri Kaski, Jukka Suomela

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer 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åk	engelska
Titel på gästpublikation	SPAA’09 : Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada
Redaktörer	Friedhelm Meyer auf der Heide, Michael A. Bender
Antal sidor	10
Förlag	ACM
Utgivningsdatum	2009
Sidor	260-269
ISBN (tryckt)	978-1-60558-606-9
DOI	https://doi.org/10.1145/1583991.1584058
Status	Publicerad - 2009
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) - Calgary, Kanada Varaktighet: 11 aug 2009 → 13 aug 2009

Vetenskapsgrenar

113 Data- och informationsvetenskap

Åtkomst av dokument

10.1145/1583991.1584058

Spaa 2009 paperAccepterat manuskript från författare, 239 KB

Citera det här

Floreen, P., Kaasinen, J., Kaski, P., & Suomela, J. (2009). An optimal local approximation algorithm for max-min linear programs. I F. Meyer auf der Heide, & M. A. Bender (Red.), SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada (s. 260-269). ACM. https://doi.org/10.1145/1583991.1584058

Floreen, Patrik ; Kaasinen, Joel ; Kaski, Petteri ; Suomela, Jukka. / An optimal local approximation algorithm for max-min linear programs. SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada. redaktör / Friedhelm Meyer auf der Heide ; Michael A. Bender. ACM, 2009. s. 260-269

@inproceedings{b0fd5d93c0f84f0883d01e28547056f3,

title = "An optimal local approximation algorithm for max-min linear programs",

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.",

keywords = "113 Computer and information sciences",

author = "Patrik Floreen and Joel Kaasinen and Petteri Kaski and Jukka Suomela",

note = " Volume: Proceeding volume: ; 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) ; Conference date: 11-08-2009 Through 13-08-2009",

year = "2009",

doi = "10.1145/1583991.1584058",

language = "English",

isbn = "978-1-60558-606-9",

pages = "260--269",

editor = "{Meyer auf der Heide}, Friedhelm and Bender, {Michael A.}",

booktitle = "SPAA{\textquoteright}09",

publisher = "ACM",

address = "International",

}

Floreen, P, Kaasinen, J, Kaski, P & Suomela, J 2009, An optimal local approximation algorithm for max-min linear programs. i F Meyer auf der Heide & MA Bender (red), SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada. ACM, s. 260-269, 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Kanada, 11/08/2009. https://doi.org/10.1145/1583991.1584058

An optimal local approximation algorithm for max-min linear programs. / Floreen, Patrik; Kaasinen, Joel; Kaski, Petteri; Suomela, Jukka.

SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada. red. / Friedhelm Meyer auf der Heide; Michael A. Bender. ACM, 2009. s. 260-269.

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

TY - GEN

T1 - An optimal local approximation algorithm for max-min linear programs

AU - Floreen, Patrik

AU - Kaasinen, Joel

AU - Kaski, Petteri

AU - Suomela, Jukka

N1 - Volume: Proceeding volume:

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - 113 Computer and information sciences

U2 - 10.1145/1583991.1584058

DO - 10.1145/1583991.1584058

M3 - Conference contribution

SN - 978-1-60558-606-9

SP - 260

EP - 269

BT - SPAA’09

A2 - Meyer auf der Heide, Friedhelm

A2 - Bender, Michael A.

PB - ACM

T2 - 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

Y2 - 11 August 2009 through 13 August 2009

ER -

Floreen P, Kaasinen J, Kaski P, Suomela J. An optimal local approximation algorithm for max-min linear programs. I Meyer auf der Heide F, Bender MA, redaktörer, SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada. ACM. 2009. s. 260-269 https://doi.org/10.1145/1583991.1584058